CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

Combinatorial Optimization
Org: Mohit Singh (McGill University)

GLENCORA BORRADAILE, Oregon State University
Finding all min st-cuts in planar graphs  [PDF]

Gomory and Hu observed that minimum st-cuts in an edge-weighted, undirected graph, for all pairs of vertices, can be represented compactly by a tree. Not only that, they showed that one can find this tree with only $n-1$ minimum cut computations. Using the duality of cuts and cycles and small, balanced separators, we show how to find such a tree for weighted, undirected planar graphs in $O(n\, \mathrm{poly}\log n)$ time.

Joint with Sankowski and Wulff-Nilsen

Adaptive Submodularity: A New Approach to Active Learning and Stochastic Optimization  [PDF]

In this talk, I will introduce a new concept called adaptive submodularity, which generalizes submodular set functions to adaptive policies.

By lifting classic results for submodular optimization problems into the adaptive realm, we recover and generalize several previous results in adaptive optimization, including results for active learning and adaptive variants of maximum coverage and set cover. Applications include machine diagnosis, observation selection and sensor placement problems, and adaptive viral marketing.

Joint work with Andreas Krause.

TOM MCCORMICK, Sauder School of Business, UBC
A Combinatorial Polynomial Algorithm for Weighted Abstract Cut  [PDF]

Hoffman and Schwartz developed Lattice Polyhedra and proved that they are totally dual integral (TDI). They abstract the cut packing dual of Shortest Path and so we call it Weighted Abstract Cut Packing (WACP). We develop the first combinatorial algorithm for WACP. It uses relaxation by a scalar parameter, and then solves a restricted abstract cut packing subproblem by using greedy cut packing and breadth-first search. This plus scaling yields a polynomial combinatorial algorithm.

GUYSLAIN NAVES, McGill University, Montreal
Mader-Mengerian graphs (joint work with Vincent Jost, École Polytechnique, France).  [PDF]

Given a graph $G$, an independent set $\mathcal{S} \subset V(G)$, when is the maximum packing of vertex-disjoint paths with extremities in $\mathcal{S}$ equal to the minimum vertex-multicut separating $\mathcal{S}$? We study a weighted generalization of this property, the total dual integrality of:

\[ \sum_{v\in P} x_v \geq 1~\textrm{for every $\mathcal{S}$-path } P \] ($x \in \mathbb{R}^{V \setminus \mathcal{S}}$). We provide characterizations in terms of forbidden minors, poly-time recognition and optimization algorithms for this TDI property.

BRUCE SHEPHERD, McGill University
Maximum Edge Disjoint Paths  [PDF]

We study the approximability of the maximum edge disjoint path problem in planar, bounded tree-width and minor-free graphs.

Handling of online submissions has been provided by the CMS.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria