Extension Complexity.

Event Date: Sep 12, 2018 in AGCO, Seminars

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 More

Strong Algorithms for the Ordinal Matroid Secretary Problem

Event Date: Sep 05, 2018 in AGCO, Seminars

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 More

A (5/3 + ε)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into Boxes

Event Date: Aug 29, 2018 in AGCO, Seminars

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 More

MST en grafos con incertidumbre y cómo encontrarlos con consultas de mínimo costo.

Event Date: Aug 22, 2018 in AGCO, Seminars

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 More

Maintaining Perfect Matchings

Event Date: Aug 08, 2018 in AGCO, Seminars

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

Sitting closer to friends than enemies, revisited

Event Date: Aug 01, 2018 in AGCO, Seminars

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