Combinatorial optimization
Organizer and Chair: Samuel Fiorini (UniversitÃ© libre de Bruxelles, Belgium)
[PDF]

Local-Search Based Approximation Algorithms for Mobile Facility Location Problems  [PDF]

In the Mobile Facility Location problem, a generalization of the classic $k$-Median problem, we are given the locations of open facilities and clients in a metric space. The goal is to move them to new locations so each client is collocated with some facility, all while minimizing the total distance travelled by all clients and facilities.

Our main result is a simple $3+\epsilon$ approximation algorithm for any constant $\epsilon \geq 0$, improving over the previous 8-approximation based on LP-rounding. This guarantee matches the best local-search based approximation for $k$-Median.

JOCHEN KOENEMANN, University of Waterloo
Finding Small Stabilizers for Unstable Graphs  [PDF]

An undirected graph G=(V,E) is stable if its inessential vertices (those that are exposed by at least one maximum matching) form a stable set. We call a set of edges F a stabilizer if its removal from G yields a stable graph. In this talk we study the following natural edge-deletion question: given a graph G, can we find a minimum-cardinality stabilizer? We show that this problem is vertex-cover hard and give efficient approximation algorithms for sparse graphs, and for regular graphs.

KANSTANTSIN PASHKOVICH, University of Waterloo
Cut Dominant and Forbidden Minors  [PDF]

We study the cut dominant which is defined as the convex hull of the characteristic vectors for all cuts in the graph plus the nonnegative orthant. The linear description of this polyhedron in its minimal integer form may involve inequalities with arbitrary large right handside. Here, we provide a characterization of the graphs for which the right handside is at most two, these are all the graphs without two fixed graphs as a minor.

Joint work with Michele Conforti and Samuel Fiorini.

LAURA SANITÃ€, University of Waterloo
Improved Region Growing and Combinatorial Algorithms for k-Route Cut Problems  [PDF]

We study the k-route generalizations of various cut problems, the most general of which is k-route multicut, wherein we have r source-sink pairs and the goal is to delete a minimum-cost set of edges to reduce the edge-connectivity of every pair to below k. We present various approximation and hardness results that improve the state-of-the-art for these problems in several cases. Our algorithms are based on combinatorial techniques and on a new, powerful region-growing approach.

Joint work with: Guru Prashanth Guruganesh and Chaitanya Swamy

TAMON STEPHEN, Simon Fraser University
The circuit diameter of the Klee-Walkup polyhedron  [PDF]

The diameter of a polyhedron is the largest number of edges in shortest paths connecting any two of its vertices. The circuit distance between two vertices is the length of the shortest walk between them that uses circuit directions, which are all the possible edge directions obtained by translation of its facets. Each circuit step is also maximal in the sense that we move along that circuit as far as we remain feasible.

We show that the Klee-Walkup polyhedron, a fundamental example for polytope diameter, has a circuit diameter satisfying the Hirsch bound. This is joint work with Timothy Yusun.