CanaDAM 2017
Université Ryerson, 12 - 16 juin 2017

Combinatorial Optimization
Org: Guyslain Naves (Aix-Marseille University) et Bruce Shepherd (McGill)

AHMAD ABDI, Waterloo
Ideal clutters that do not pack  [PDF]

We prove that among ideal minimally non-packing (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 non-packing 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 root-sets $R_1,\dots ,R_k$. Recently, we characterized digraphs admitting $k$ disjoint branchings for which, rather than the root-sets, their sizes $\mu _1,\dots ,\mu _k$ are specified. The proof was not algorithmic as it used a general min-max 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 Urbana-Champaign
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 $G-E'/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 LP-based constant factor approximation algorithm for subset feedback vertex set.

Multi-agent 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 multi-agent 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 multi-agent problems are linked to their single-agent primitives.

BRUCE SHEPHERD, McGill University
Conflict-Free 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.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Ryerson Office of Naval Research Science and Technology