CanaDAM 2021
On-line, May 25 - 28, 2021

Combinatorial Optimization - Part II
Org: László Végh (London School of Economics)

SAMI DAVIES, University of Washington
Scheduling with Communication Delays via LP Hierarchies and Clustering  [PDF]

We study scheduling with precedence constraints and communication delays. Here, if two dependent jobs are scheduled on different machines, then $c$ time units must pass between their executions. Previously, the best known approximation ratio was $O(c)$, though an open problem in the top-10 list by Schuurman and Woeginger asks whether there exists a constant-factor approximation algorithm. We give a polynomial-time $O(\log c \cdot \log m)$-approximation algorithm when given $m$ identical machines and delay $c$ for minimizing makespan. Our approach uses a Sherali-Adams lift of an LP relaxation and a clustering of the semimetric space induced by the lift.

SHARAT IBRAHIMPUR, University of Waterloo
Approximation Algorithms for Stochastic Minimum Norm Combinatorial Optimization  [PDF]

In this work, we introduce and study stochastic minimum-norm optimization. We have an underlying combinatorial optimization problem where the costs involved are random variables with given distributions; each feasible solution induces a random multidimensional cost vector. We seek a solution that minimizes the expected norm of the induced cost vector, for a given monotone, symmetric norm. We give a general framework for devising approximation algorithms for stochastic minimum-norm optimization, using which we obtain approximation algorithms for the stochastic minimum-norm versions of the load balancing and spanning tree problems.

Based on joint work with Chaitanya Swamy.

NATHAN KLEIN, University of Washington
Approximating the minimum $k$-edge connected multi-subgraph problem  [PDF]

Here we are given a weighted graph and wish to find a minimum cost $k$-edge connected spanning subgraph. Our subgraph may use the same edge multiple times. While for unweighted graphs a $1+O(1/k)$ approximation is known, the weighted case only has a 3/2 approximation from the 80s. We show a simple $1+o(1)$ approximation as $k$ goes to infinity, demonstrating that the problem gets easier as $k$ grows. The entire (elementary) analysis will be explained in this talk and serves as a gentle introduction to Strongly Rayleigh distributions.

Based on joint work with Anna Karlin, Shayan Oveis Gharan, and Xinzhi Zhang.

ZHUAN KHYE KOH, London School of Economics
An Accelerated Newton-Dinkelbach Method and its Application to Two Variables Per Inequality Systems  [PDF]

In this talk, I will present an accelerated, or ‘look-ahead’ version of the Newton-Dinkelbach method, a well-known technique for solving fractional and parametric optimization problems. This acceleration halves the Bregman divergence between the current iterate and the optimal solution within every two iterations. Using the Bregman divergence as a potential in conjunction with combinatorial arguments, we obtain a strongly polynomial label-correcting algorithm for solving linear feasibility systems with two variables per inequality. This extends and strengthens a previous result by Madani (2002).

Based on joint work with Daniel Dadush, Bento Natura and László Végh.

Improving the Approximation Ratio for Capacitated Vehicle Routing  [PDF]

We devise a new approximation algorithm for capacitated vehicle routing. Our algorithm yields a better approximation ratio for general capacitated vehicle routing as well as for the unit-demand case and the splittable variant. Our results hold in arbitrary metric spaces. This is the first improvement on the classical tour partitioning algorithm by Haimovich and Rinnooy Kan [1985] and Altinkemer and Gavish [1987].

This is joint work with Jannis Blauth and Jens Vygen.