Noticias en español
A Median-Type Condition for Graph Tiling
Abstract: Komlos determined the asymptotically optimal minimum degree condition for covering a given proportion of vertices of a host graph by vertex-disjoint copies of a fixed graph H. We show that the minimum degree condition can be relaxed in the sense that we require only a given fraction of vertices to have the prescribed degree. Joint work with Diana Piguet.
Read MoreExtension 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 More