An optimal local approximation algorithm for max-min linear programs


الملخص بالإنكليزية

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.

تحميل البحث