Combinatorial optimization
Organizer and Chair:
Samuel Fiorini (UniversitÃ© libre de Bruxelles, Belgium)
[
PDF]
 ZACHARY FRIGGSTAD, University of Alberta
LocalSearch 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 8approximation based on LProunding. This guarantee matches the best localsearch 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 edgedeletion question: given a graph G, can we find a minimumcardinality stabilizer? We show that this problem is vertexcover 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 kRoute Cut Problems [PDF]

We study the kroute generalizations of various cut problems, the most general of which is kroute multicut, wherein we have r sourcesink pairs and the goal is to delete a minimumcost set of edges to reduce the edgeconnectivity of every pair to below k. We present various approximation and hardness results that improve the stateoftheart for these problems in several cases. Our algorithms are based on combinatorial techniques and on a new, powerful regiongrowing approach.
Joint work with: Guru Prashanth Guruganesh and Chaitanya Swamy
 TAMON STEPHEN, Simon Fraser University
The circuit diameter of the KleeWalkup 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 KleeWalkup polyhedron, a fundamental example
for polytope diameter, has a circuit diameter satisfying the Hirsch bound.
This is joint work with Timothy Yusun.