A Distributed Approximation Algorithm for Mixed Packing-Covering Linear Programs

Faraz Makari, Rainer Gemulla
Max-Planck-Institut fur Informatik
NIPS Biglearn workshop, 2013


   title={A Distributed Approximation Algorithm for Mixed Packing-Covering Linear Programs},

   author={Makari, Faraz and Gemulla, Rainer},



Download Download (PDF)   View View   Source Source   



Mixed packing-covering linear programs capture a simple but expressive subclass of linear programs. They commonly arise as linear programming relaxations of a number important combinatorial problems, including various network design and generalized matching problems. In this paper, we propose an efficient distributed approximation algorithm for solving mixed packing-covering problems which requires a poly-logarithmic number of passes over the input. Our algorithm is well-suited for parallel processing on GPUs, in shared-memory architectures, or on small clusters of commodity nodes. We report results of a case study for generalized bipartite matching problems.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: