An optimal local approximation algorithm for max-min linear programs

Patrik Floréen, Joel Kaasinen, Petteri Kaski +1

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$…