Brief announcement: Stateless distributed algorithms for generalized packing linear programs

Abstract

We develop a framework of distributed and stateless solutions for implicitly given packing linear programs, which are solved by multiple agents operating in a cooperative but uncoordinated manner. This is motivated by multi-commodity flow problems where flows can be split along possibly exponentially many paths. Compared to explicitly given packing LPs, the main challenge here lies in the exponentially (or even infinitely) many variables handled by a single agent. An efficient algorithm thus must identify a few "good" variables to update. Using a notion similar to the shortest-path-first-flow-decomposition, our algorithm discovers polynomially many variables to update in each iteration. We prove that after polynomially many rounds, the discovered variables support a near-optimal solution to the given packing LP.