28/08/2015
Universidad de Buenos Aires
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
Universidad de Chile, Chile
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
Institute of Technology de la Universidad de Washington, Tacoma
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.
.