CanaDAM 2011 University of Victoria, May 31 - June 3, 2011 www.cms.math.ca//2011

Combinatorial Optimization
Org: Mohit Singh (McGill University)
[PDF]

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

DAN GOLOVIN, Caltech
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.