CanaDAM 2021
En ligne, 25 - 28 mai 2021

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

Block-Structured Integer and Linear Programming in Near Linear Time  [PDF]

We consider \emph{integer} and \emph{linear programming} problems for which the linear constraints exhibit a block-structure: The problem decomposes into independent small subproblems if a few constraints are deleted.

For linear programming, our algorithm relies on the \emph{parametric search} framework by Norton, Plotkin, and Tardos in combination with Megiddo's multidimensional search technique. This also forms a subroutine for integer programming. We use a strong linear relaxation and present a \emph{proximity bound} between the respective optima that is independent of the dimension.

We apply our results to $n$-fold integer programs, obtaining algorithms that are near-linear in the dimension and strongly polynomial.

EDIN HUSIĆ, London School of Economics
Approximating Nash Social Welfare under Rado Valuations  [PDF]

Nash social welfare (NSW) is defined as the geometric mean of agents' valuations. We consider the problem of approximating maximum NSW while allocating indivisible items to agents. We present the first constant-factor approximation algorithm for the problem when agents have Rado valuations -- a general class of valuation functions that arise from maximum cost independent matching problems, including as special cases assignment (OXS) valuations and weighted matroid rank functions. Our approach also extends to the asymmetric NSW (weighted geometric mean) under Rado valuations with approximation guarantees depending on the maximum weight.

JASON LI, Carnegie Mellon University
Deterministic Mincut in Almost-Linear Time  [PDF]

We present a deterministic (global) mincut algorithm for weighted, undirected graphs that runs in $m^{1+o(1)}$ time, answering an open question of Karger from the 1990s. To obtain our result, we de-randomize the construction of the skeleton graph in Karger’s near-linear time mincut algorithm, which is its only randomized component. In particular, we partially de-randomize the well-known Benczur-Karger graph sparsification technique by random sampling, which we accomplish by the method of pessimistic estimators. Our main technical component is designing an efficient pessimistic estimator to capture the cuts of a graph, obtained by the expander decomposition framework (Goranci et al.)

KENT QUANRUD, Purdue University
Faster Algorithms for Rooted Connectivity in Directed Graphs  [PDF]

We consider the fundamental problems of determining the rooted and global edge and vertex connectivities (and computing the corresponding cuts) in directed graphs. For rooted (and hence also global) edge connectivity we give a new randomized Monte Carlo reduction to $(s,t)$-flow, resulting in new randomized algorithms for simple graphs. Similarly we obtain new randomized running times for rooted and global vertex connectivity in directed graphs. Our results are based on a simple combination of sampling coupled with sparsification that appears new, and could lead to further tradeoffs for directed graph connectivity problems.

This is joint work with Chandra Chekuri.

SAHIL SINGLA, Princeton University and Institute for Advanced Study
Improved Truthful Mechanisms for Combinatorial Auctions  [PDF]

A longstanding open problem in Algorithmic Mechanism Design is to design computationally efficient truthful mechanisms for (approximately) maximizing welfare in combinatorial auctions with submodular/subadditive bidders. This problem has been studied extensively since the first mechanisms by Dobzinski, Nisan, and Schapira [STOC'05, STOC’06], culminating in an $O(\sqrt{\log m})$-approximation for submodular and an $O(\log m \cdot \log\log m)$-approximation for subadditive bidders, where m is the number of items. We present computationally-efficient truthful mechanisms with exponentially improved approximation ratios: an $O((\log\log m)^3)$-approximation for subadditive and an $O((\log\log m)^2)$-approximation for submodular bidders.

Based on joint works with Sepehr Assadi and Thomas Kesselheim [FOCS'19, SODA'21].