CanaDAM 2013 Memorial University of Newfoundland, June 10 - 13, 2013 www.cms.math.ca//2013

Optimization
Chair: Bruce Shepherd (McGill University)
[PDF]

Integer flows in binary matroids  [PDF]

Geelen and Guenin proved that the cut condition is both sufficient and necessary for the existence of an integer multi-commodity flow for instances that are Eulerian and do not contain a special obstruction. This result was predicted as a special case of the 1977 Cycling Conjecture of Seymour, on the existence of certain integer flows in binary matroids. We consider this conjecture for the case of lifts of graphic matroids, and prove a far reaching generalization to the multi-commodity flow result of Geelen and Guenin with applications to graph coloring and graph homomorphism.

This is joint work with Bertrand Guenin.

ZHIHAN GAO, Department of Combinatorics and Optimization, University of Waterloo
An LP-based 3/2-approximation algorithm for the graphic s-t path TSP  [PDF] [SLIDES]

The Traveling Salesman Problem (TSP) is one of the most famous problems in Combinatorial Optimization. Given two vertices $s, t$ in a graph $G$ with unit edge-cost, the graphic $s$-$t$ path TSP is to find a minimum-cost Hamiltonian path from $s$ to $t$ in the metric completion of $G$. For the graphic $s$-$t$ path TSP, we design a new LP-based algorithm, which achieves the best approximation factor of $1.5$. The algorithm is based on the idea of narrow cuts due to An, Kleinberg, and Shmoys (STOC 2012). It partly answers an open question of Seb\H{o} (IPCO 2013).

JOHN GOLDWASSER, West Virginia University
Maximum density of exact copies of a subgraph of the d-cube in the n-cube  [PDF] [SLIDES]

Let H be a subgraph of the d-cube. If J is a subgraph of a large n-cube, what is the maximum density of d-cube subgraphs of the n-cube whose intersection with J is precisely H? We answer this question when H is a perfect matching of parallel edges. We discuss the difficulties when H is a single edge. We show the maximum density is 15/16 when H is a single edge in the 2-cube, with host graph a large Hamming ball of radius 3, rather than the n-cube.

TOM MCCORMICK, UBC Sauder School of Business
A parametric min cut approximation algorithm for network inhibition  [PDF] [SLIDES]

A natural problem in networks is Network Inhibition: Given a cost for destroying each arc and a budget B, destroy a (possibly fractional) set of arcs D such that the max flow in the remaining network is minimized. This problem is NP Hard, but Burch et al show how to get a good pseudo-approximation algorithm via linear programming.

We show how to implement and extend their algorithm combinatorially using parametric min cut computations. This involves showing a conjugate duality relationship between Network Inhibition and a parametric max flow problem.

Joint work with Oriolo, Peis, Stiller and Garasto.

BRUCE SHEPHERD, McGill University
Almost-tight Bounds for Online Vector Bin Packing  [PDF]

In the $d$-dimensional bin packing problem (VBP), one is given vectors $x_1,x_2, \ldots ,x_n \in [0,1]^d$ and the goal is to find a partition into a minimum number of feasible sets, i.e., sets that fit into a $d$-dimensional bin $1^d$.

It has been outstanding for 20 years to clarify the gap between the best lower bound on the competitive ratio (of 2) versus the best upper bound of $O(d)$ (Garey,Graham, Johnson, Rao 1976). We show a lower bound of $d^{1-\epsilon}$ for any $\epsilon > 0$.

(joint with Y. Azar, I. Cohen, S. Kamara)