# Seminario 2015-2018

28/08/2015

**Flavia Bonomo**

Universidad de Buenos Aires

**"3-Coloreo de grafos sin triángulos ni caminos inducidos de longitud 7"**

El problema de coloreo de grafos es usado habitualmente para modelar diversos
problemas reales. Vamos a hablar en esta charla sobre coloreo en grafos con
subgrafos inducidos prohibidos, y en particular 3-coloreo de grafos sin triángulos
ni caminos inducidos de longitud 7.

Este es un trabajo conjunto con Maria Chudnovsky,
Peter Maceli, Oliver Schaudt, Maya Stein y Mingxian Zhong.

14/11/2017

**Andreas Wiese**

Universidad de Chile, Chile

**"Parameterized (1+eps)-approximation algorithms for packing problems"**

Approximation algorithms and parameterized algorithms are two well-established ways to deal with NP-hard problems. In the first case, the goal is to compute in polynomial time a solution of cost close to the optimum. In the second case, the goal is to compute an optimal solution in (FPT) time f(k)n^O(1), where k is some parameter of the input. The recent area of parameterized approximation seeks to combine the two approaches by, e.g., aiming for (1+eps)-approximations in f(k,eps)n^g(eps) time.

We present such algorithms for three important packing problems: for the Maximum Independent Set of Rectangles problem, for the Unsplittable Flow on a Path problem, and for the Two-Dimensional Knapsack problem with rotations. All three problems are W[1]-hard and hence we do not expect to find an FPT algorithm for them. Also, it seems very difficult to construct a PTAS for them which motivates studying parameterized (1+eps)-approximations for them.

Joint work with Fabrizio Grandoni and Stefan Kratsch.

08/02/2018

**Moshe Rosenfeld**

Institute of Technology de la Universidad de Washington, Tacoma

**"Starters what you know or would like to learn: old and new open problems"**

Let G be an Abelian group of odd order. A starter in G is a partition
of G \ {0} into disjoint pairs {a_1 , b_1 }, \ldots , {a_n , b_n } such that:

1. \cup_{i =1}^n { ± (a_i - b_i) } = G \ {0}.

2. {±(a_i - b_i)} \cap {± (a_j - b_j)} = \emptyset

Starters are frequently used as tools in many combinatorial designs. In this talk I will discuss mostly starters in Z_{2n+1}. I will survey some known starter open problems and their status and introduce a few new ones.
.

<<

####