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.

REFERENCES

• 1: Baruch Awerbuch , Rohit Khandekar, Greedy distributed optimization of multi-commodity flows, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281140]
• 2: Baruch Awerbuch , Rohit Khandekar, Stateless distributed gradient descent for positive linear programs, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374476]
• 3: Serge A. Plotkin , David B. Shmoys , Éva Tardos, Fast approximation algorithms for fractional packing and covering problems, Mathematics of Operations Research, v.20 n.2, p.257-301, May 1995 [doi>10.1287/moor.20.2.257]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

General Terms:
Algorithms, Theory

Keywords:
distributed and stateless algorithms, fast convergence, gradient descent, linear programming