Combinatorial Optimization
Org:
Guyslain Naves (AixMarseille University) and
Bruce Shepherd (McGill)
[
PDF]
 AHMAD ABDI, Waterloo
Ideal clutters that do not pack [PDF]

We prove that among ideal minimally nonpacking (mnp) clutters, those with covering number 2 play a central role; a qualitative characterization theorem for these clutters is also proved. At the core of this characterization lies a class of objects, called marginal cuboids, that naturally give rise to ideal nonpacking clutters with covering number 2. We present an explicit class of marginal cuboids, and provide an excluded minor characterization for it, where one of the excluded minors is a new ideal mnp clutter on 10 elements. Joint work with Gerard Cornuejols and Kanstantsin Pashkovich.
 ANDRAS FRANK, Eotvos Lorand University
Finding $k$ disjoint branchings with specified sizes [PDF]

Edmonds' disjoint branching theorem characterized digraphs including
$k$ disjoint branchings with prescribed rootsets $R_1,\dots ,R_k$.
Recently, we characterized digraphs admitting $k$ disjoint branchings
for which, rather than the rootsets, their sizes $\mu _1,\dots ,\mu
_k$ are specified. The proof was not algorithmic as it used a general
minmax theorem on covering a crossing supermodular function by
directed graphs. We will describe a purely graph
theoretical algorithm for computing the $k$ branchings in question
when they exist or the obstacle provided by the theorem when the
branchings do not exist.
The talk is based on a joint work with K. B\'erczi.
 VIVEK MADAN, Uuniversity Illininois UrbanaChampaign
Revisiting Cut problems and Labelling LPs [PDF]

A cut problem is specified by a graph $G$ and property $X$. The goal is to remove edges/vertices ($E'/V'$) such that the remaining graph satisfies property $X$. We investigate a labeling view of some of the cut problems based on the structural properties of $GE'/V'$ and improve existing results. In particular, we study multiway cut, multicut and subset feedback set problems. Some of the results include simpler approximation algorithm for multiway cut, unique games hardness of $k\epsilon$ for seperating $k$ pairs in directed graph, and a new LPbased constant factor approximation algorithm for subset feedback vertex set.
 RICHARD SANTIAGO, McGill University
Multiagent Submodular Optimization [PDF]

Recent years have seen many algorithmic advances in the area of submodular optimization: $\min/\max~f(S): S \in \mathcal{F}$, where $f$ is submodular and $\mathcal{F}$ a family of feasible sets. Our focus is on a more general class of multiagent submodular optimization problems introduced by Goel et al. in the minimization setting: $\min \sum_i f_i(S_i): S_1+S_2+ \cdots +S_k \in \mathcal{F}$. Here $+$ denotes disjoint union and hence this model is attractive where resources are being allocated across $k$ agents. In this talk we explore the extent to which the approximability of the multiagent problems are linked to their singleagent primitives.
 BRUCE SHEPHERD, McGill University
ConflictFree Disjoint Paths and Stable Matchings [PDF]

We outline a subroutine needed in the recent work on confluent flows with Adrian Vetta and Gord Wilfong. It asks for flows with the following flavour. Nodes are partitioned into "conflict cliques" and we may use at most one node from any given clique.