A Simple Boosting Framework for Transshipment
OPEN ACCESS
Author / Producer
Date
2023-08-30
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
Transshipment is an important generalization of both the shortest path problem and the optimal transport problem. The task asks to route a demand using a flow of minimum cost over (uncapacitated) edges. Transshipment has recently received extensive attention in theoretical computer science as it is the centerpiece of all modern theoretical breakthroughs in parallel and distributed (approximate) shortest-path computation, a classic and well-studied problem. The key advantage of transshipment over shortest paths is the so-called boosting property: one can often boost a crude approximate solution to a (near-optimal) (1 + ε)-approximate solution. However, our understanding of this phenomenon is limited: it is not clear which approximators can be boosted. Moreover, all current boosting frameworks are built with a specific type of approximator in mind and are relatively complicated. The main takeaway of our paper is conceptual: any black-box oracle that computes an approximate dual solution can be boosted to an (1 + ε)-approximator. This decouples and simplifies all known near-optimal (1 + ε)-approximate transshipment and shortest paths results: they all (implicitly) construct approximate dual solutions and boost them. We provide a very simple analysis based on the multiplicative weights framework. Furthermore, to keep the paper completely self-contained, we provide a new (and arguably much simpler) analysis of multiplicative weights that leverages well-known optimization tools to bypass the ad-hoc calculations used in the standard analyses.
Permanent link
Publication status
published
External links
Book title
31st Annual European Symposium on Algorithms (ESA 2023)
Volume
274
Pages / Article No.
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
31st Annual European Symposium on Algorithms (ESA 2023)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Mixed continuous-discrete optimization; Boosting; Multiplicative weights; Theoretical computer science; Shortest path; Parallel algorithms
Organisational unit
08730 - Gruppe Häupler / Group Häupler