Noticias en español
Extension Complexity.
Abstract: A polytope Q is called an extension of a polytope P if P is a projection of Q. The extension complexity of a polytope is the minimum number of inequalities needed to describe any of its extensions. In this talk I will describe some results related to extension complexities of several important polytopes arising in combinatorial optimization and discuss how extension complexity can be used to model computational difficulty of solving problems.
Read MoreStrong Algorithms for the Ordinal Matroid Secretary Problem
Abstract: A general technique and analysis for the matroid secretary problem is presented and then we show how to achieve a 4-competitive algorithm for the case of graphic matroids.
Read MoreA (5/3 + ε)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into Boxes
Abstract: In the unsplittable flow on a path problem (UFP) we are given a path with edge capacities and a collection of tasks. Each task is characterized by a subpath, a profit, and a demand. Our goal is to compute a maximum profit subset of tasks such that, for each edge e, the total demand of selected tasks that use e does not exceed the capacity of e. The current best polynomial-time approximation factor for this problem is 2 + eps for any constant eps>0. This is the best known factor even in the case of uniform edge capacities. These results, likewise most prior work, are based on a...
Read MoreMST en grafos con incertidumbre y cómo encontrarlos con consultas de mínimo costo.
Abstract: En esta presentación estudiaremos el problema de MST en un contexto donde los pesos son inciertos. Dado un grafo, para cada arista se conocerá un conjunto no vacío que contiene los posibles pesos de la arista. Eventualmente los verdaderos pesos se darán a conocer y llamamos a esto una realización de los pesos. Los algoritmos a considerar tendrán acceso a una operación especial llamada “consulta” que revela de manera inmediata el verdadero peso de una arista a cierto costo predeterminado. Nos enfocaremos en los siguientes problemas: – El problema de MST uniforme;...
Read MoreMaintaining Perfect Matchings
Abstract: We investigate the minimum-cost perfect matching problem in metric spaces with two stages. In the first stage, an algorithm is confronted with a set of points from a metric space and ought to find a perfect matching among them. Subsequently, an adversary can announce new points after which the algorithm has to give a perfect matching on the extended set. However, for every arrived point, the algorithm can only do a constant number of reallocations with respect to the old matching. We call an algorithm for this problem (two-stage) robust if the cost of each matching is within a...
Read MoreSitting closer to friends than enemies, revisited
Abstract: The Sitting Closer to Friends than Enemies problem is to find an embedding in a metric space for the vertices of a given signed graph so that, for every pair of incident edges with different sign, the positive edge has to be shorter (in the metric of the space) than the negative edge. In this talk, I will give a gentle introduction and will present a collection of results regarding this problem. In particular, I will show a characterization for the sets of signed graphs for which there exist such an embedding in \mathbb{R}, in the circle, and in trees. Moreover, I will show an...
Read More