A Simple Boosting Framework for Transshipment
Abstract
Transshipment, also known under the names of earth mover's distance, uncapacitated min-cost flow, or Wasserstein's metric, is an important and well-studied problem that asks to find a flow of minimum cost that routes a general demand vector. Adding to its importance, recent advancements in our understanding of algorithms for transshipment have led to breakthroughs for the fundamental problem of computing shortest paths. Specifically, the recent near-optimal $(1+\eps)$-approximate single-source shortest path algorithms in the parallel and distributed settings crucially solve transshipment as a central step of their approach.
The key property that differentiates transshipment from other similar problems like shortest path is the so-called \emph{boosting}: one can boost a (bad) approximate solution to a near-optimal $(1 + \eps)$-approximate solution. This conceptually reduces the problem to finding an approximate solution. However, not all approximations can be boosted---there have been several proposed approaches that were shown to be susceptible to boosting, and a few others where boosting was left as an open question.
The main takeaway of our paper is that any black-box $\alpha$-approximate transshipment solver that computes a \emph{dual} solution can be boosted to an $(1 + \eps)$-approximate solver. Moreover, we significantly simplify and decouple previous approaches to transshipment (in sequential, parallel, and distributed settings) by showing all of them (implicitly) obtain approximate dual solutions.
Our analysis is very simple and relies only on the well-known 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.
The key property that differentiates transshipment from other similar problems like shortest path is the so-called \emph{boosting}: one can boost a (bad) approximate solution to a near-optimal $(1 + \eps)$-approximate solution. This conceptually reduces the problem to finding an approximate solution. However, not all approximations can be boosted---there have been several proposed approaches that were shown to be susceptible to boosting, and a few others where boosting was left as an open question.
The main takeaway of our paper is that any black-box $\alpha$-approximate transshipment solver that computes a \emph{dual} solution can be boosted to an $(1 + \eps)$-approximate solver. Moreover, we significantly simplify and decouple previous approaches to transshipment (in sequential, parallel, and distributed settings) by showing all of them (implicitly) obtain approximate dual solutions.
Our analysis is very simple and relies only on the well-known 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.
Research Areas
