## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, March 01, 2022, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Goran Zuzic

## A Simple Boosting Framework for Transshipment

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 approximate shortest paths in parallel and distributed settings. The key property that differentiates transshipment from other similar problems like the 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. In this talk, I will show how 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.

Information for students and suggested topics for student talks