Fast, Distributed Approximation Algorithms for Positive Linear Programming with Applications to Flow Control

Abstract

We study combinatorial optimization problems in which a set of distributed agents must achieve a global objective using only local information. Papadimitriou and Yannakakis [15] initiated the study of such problems in a framework where distributed decision-makers must generate feasible solutions to positive linear programs with information only about local constraints. We extend their model by allowing these distributed decision-makers to perform local communication to acquire information over time and then explore the tradeo between the amount of communication and the quality of the solution to the linear program that the decision makers can obtain. Our main result is a distributed algorithm that obtains a (1 ) approximation to the optimal linear programming solution while using only a polylogarithmic number of rounds of local communication. This algorithm oers a signi cant improvement over the logarithmic approximation ratio previously obtained by [3] for this problem while prov...