Document Open Access Logo

Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^{-3}) Time

Authors Michael W. Mahoney, Satish Rao, Di Wang, Peng Zhang

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.52.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Michael W. Mahoney
Satish Rao
Di Wang
Peng Zhang

Cite As Get BibTex

Michael W. Mahoney, Satish Rao, Di Wang, and Peng Zhang. Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^{-3}) Time. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.52

Abstract

We study the problem of approximately solving positive linear programs (LPs). This class of LPs models a wide range of fundamental problems in combinatorial optimization and operations research, such as many resource allocation problems, solving non-negative linear systems, computing tomography, single/multi commodity flows on graphs, etc. For the special cases of pure packing or pure covering LPs, recent result by Allen-Zhu and Orecchia [Allen/Zhu/Orecchia, SODA'15] gives O˜(1/(epsilon^3))-time parallel algorithm, which breaks the longstanding O˜(1/(epsilon^4)) running time bound by the seminal work of Luby and Nisan [Luby/Nisan, STOC'93]. 

We present new parallel algorithm with running time O˜(1/(epsilon^3)) for the more general mixed packing and covering LPs, which improves upon the O˜(1/(epsilon^4))-time algorithm of Young [Young, FOCS'01; Young, arXiv 2014]. Our work leverages the ideas from both the optimization oriented approach [Allen/Zhu/Orecchia, SODA'15; Wang/Mahoney/Mohan/Rao, arXiv 2015], as well as the more combinatorial approach with phases [Young, FOCS'01; Young, arXiv 2014]. In addition, our algorithm, when directly applied to pure packing or pure covering LPs, gives a improved running time of O˜(1/(epsilon^2)).

Subject Classification

Keywords
  • Mixed packing and covering
  • Linear program
  • Approximation algorithm
  • Parallel algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Zeyuan Allen-Zhu and Lorenzo Orecchia. Nearly-linear time positive LP solver with faster convergence rate. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC'15, pages 229-236, 2015. Newer version available at URL: http://arxiv.org/abs/1411.1124.
  2. Zeyuan Allen-Zhu and Lorenzo Orecchia. Using optimization to break the epsilon barrier: A faster and simpler width-independent algorithm for solving positive linear programs in parallel. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'15, pages 1439-1456, 2015. Google Scholar
  3. Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing, 8(6):121-164, 2012. URL: http://www.theoryofcomputing.org/articles/v008a006, URL: http://dx.doi.org/10.4086/toc.2012.v008a006.
  4. Baruch Awerbuch and Rohit Khandekar. Stateless distributed gradient descent for positive linear programs. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 691-700, 2008. Google Scholar
  5. S. Boyd and L. Vandenberghe. Convex Optimization. Camebridge University Press, 2004. Google Scholar
  6. Lisa Fleischer. A fast approximation scheme for fractional covering problems with variable upper bounds. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004, pages 1001-1010, 2004. Google Scholar
  7. Christos Koufogiannakis and Neal E. Young. A nearly linear-time PTAS for explicit fractional packing and covering linear programs. Algorithmica, 70(4):648-674, 2014. URL: http://dx.doi.org/10.1007/s00453-013-9771-6.
  8. Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in õ(sqrt(rank)) iterations and faster algorithms for maximum flow. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 424-433, 2014. Google Scholar
  9. Yin Tat Lee and Aaron Sidford. Efficient inverse maintenance and faster algorithms for linear programming. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 230-249, 2015. Google Scholar
  10. Michael Luby and Noam Nisan. A parallel approximation algorithm for positive linear programming. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 448-457, 1993. Google Scholar
  11. Faraz Makari Manshadi, Baruch Awerbuch, Rainer Gemula, Rohit Khandekar, Julián Mestre, and Mauro Sozio. A distributed algorithm for large-scale generalized matching. PVLDB, 6(9):613-624, 2013. Available at http://www.vldb.org/pvldb/vol6/p613-makarimanshadi.pdf. Google Scholar
  12. Arkadi Nemirovski. Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251, 2004. URL: http://dx.doi.org/10.1137/S1052623403425629.
  13. Yurii Nesterov. Smooth minimization of non-smooth functions. Math. Program., 103(1):127-152, 2005. URL: http://dx.doi.org/10.1007/s10107-004-0552-5.
  14. Yurii Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341-362, 2012. URL: http://dx.doi.org/10.1137/100802001.
  15. Richard Peng and Kanat Tangwongsan. Faster and simpler width-independent parallel algorithms for positive semidefinite programming. In Proceedinbgs of the 24th ACM symposium on Parallelism in algorithms and architectures, SPAA '12, pages 101-108, 2012. Available at http://arxiv.org/abs/1201.5135. Google Scholar
  16. James Renegar. Efficient first-order methods for linear programming and semidefinite programming. CoRR, abs/1409.5832, 2014. URL: http://arxiv.org/abs/1409.5832.
  17. Di Wang, Michael W. Mahoney, Nishanth Mohan, and Satish Rao. Faster parallel solver for positive linear programs via dynamically-bucketed selective coordinate descent. CoRR, abs/1511.06468, 2015. URL: http://arxiv.org/abs/1511.06468.
  18. Neal E. Young. Sequential and parallel algorithms for mixed packing and covering. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 538-546, 2001. Google Scholar
  19. Neal E. Young. Nearly linear-time approximation schemes for mixed packing/covering and facility-location linear programs. CoRR, abs/1407.3015, 2014. URL: http://arxiv.org/abs/1407.3015.
  20. Zeyuan Allen Zhu, Yin Tat Lee, and Lorenzo Orecchia. Using optimization to obtain a width-independent, parallel, simpler, and faster positive SDP solver. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1824-1831, 2016. Available at http://arxiv.org/abs/1507.02259. Google Scholar
  21. Zeyuan Allen Zhu and Lorenzo Orecchia. Linear coupling: An ultimate unification of gradient and mirror descent. CoRR, abs/1407.1537, 2014. URL: http://arxiv.org/abs/1407.1537.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact