An optimal local approximation algorithm for max-min linear programs

Abstract

We present a local algorithm (constant-time distributed algorithm) for approximating max-min LPs. The objective is to maximise $\omega$ subject to $Ax\le 1$, $Cx\ge \omega 1$, and $x\ge 0$ for nonnegative matrices $A$ and $C$. The approximation ratio of our algorithm is the best possible for any local algorithm; there is a matching unconditional lower bound.

16 pages, 3 figures

References in corpus (4)

• Sequential and Parallel Algorithms for Mixed Packing and Covering
• Approximating max-min linear programs with local algorithms
• Tight local approximation results for max-min linear programs
• Local approximation algorithms for a class of 0/1 max-min linear programs

Cited by in corpus (3)

• Weak Models of Distributed Computing, with Connections to Modal Logic
• Tight local approximation results for max-min linear programs
• Local Distributed Verification