A parallel approximation algorithm for positive linear programming

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A parallel approximation algorithm for positive linear programming

Full text

Pdf (616 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 448 - 457

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Michael Luby
Noam Nisan

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 41, Citation Count: 29

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/167088.167211 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Bonnie Berger , John Rompel , Peter W. Shor, Efficient NC algorithms for set cover with applications to learning and geometry, Proceedings of the 30th IEEE symposium on Foundations of computer science, p.454-477, December 1994, Research Triangle Park, North Carolina, United States
	2	Chazelle, B., Friedman, J., "A Deterministic View of Random Sampling and its Use in Geometry", Princeton Technical Report No. CS- TR-436, September i988. A preliminary version appears in FOCS 1988.
	3	Cohen, E., "Approximate max flow on small depth networks", FOCS, 1992, pp. 648-658.
	4	Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
	5	Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
	6	Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
	7	Lund, C., Yannakakis, M., "On the Hardness of Approximating Minimization Problems", preprint.
	8	Serge A. Plotkin , David B. Shmoys , Eva Tardos, Fast approximation algorithms for fractional packing and covering problems, Stanford University, Stanford, CA, 1993
	9	Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]

CITED BY 29

	Uriel Feige , Joe Kilian, Making games short (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.506-516, May 04-06, 1997, El Paso, Texas, United States
	Edo Zurel , Noam Nisan, An efficient approximate allocation algorithm for combinatorial auctions, Proceedings of the 3rd ACM conference on Electronic Commerce, p.125-136, October 14-17, 2001, Tampa, Florida, USA
	Aravind Srinivasan, New approaches to covering and packing problems, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.567-576, January 07-09, 2001, Washington, D.C., United States
	Suresh Chari , Pankaj Rohatgi , Aravind Srinivasan, Improved algorithms via approximations of probability distributions (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.584-592, May 23-25, 1994, Montreal, Quebec, Canada
	Maria Serna , Fatos Xhafa, Approximating Scheduling Unrelated Parallel Machines in Parallel, Computational Optimization and Applications, v.21 n.3, p.325-338, March 2002
	Michael Elkin, Distributed approximation: a survey, ACM SIGACT News, v.35 n.4, December 2004
	Lujun Jia , Rajmohan Rajaraman , Torsten Suel, An efficient distributed algorithm for constructing small dominating sets, Distributed Computing, v.15 n.4, p.193-205, December 2002
	Neal E. Young, Randomized rounding without solving the linear program, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.170-178, January 22-24, 1995, San Francisco, California, United States
	Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, The price of being near-sighted, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.980-989, January 22-26, 2006, Miami, Florida
	Biing-Feng Wang, Finding r-Dominating Sets and p-Centers of Trees in Parallel, IEEE Transactions on Parallel and Distributed Systems, v.15 n.8, p.687-398, August 2004
	Fabian Kuhn , Roger Wattenhofer, Constant-time distributed dominating set approximation, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.25-32, July 13-16, 2003, Boston, Massachusetts
	Baruch Awerbuch , Mohammad T. Hajiaghayi , Robert D. Kleinberg , Tom Leighton, Online client-server load balancing without global information, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Thomas Moscibroda , Roger Wattenhofer, Facility location: distributed approximation, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Guy Even , Dror Rawitz , Shimon Shahar, Hitting sets when the VC-dimension is small, Information Processing Letters, v.95 n.2, p.358-362, 31 July 2005
	Fabian Kuhn , Roger Wattenhofer, Constant-time distributed dominating set approximation, Distributed Computing, v.17 n.4, p.303-310, May 2005
	Harald Räcke, Optimal hierarchical decompositions for congestion minimization in networks, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Maria Serna , Luca Trevisan , Fatos Xhafa, The approximability of non-Boolean satisfiability problems and restricted integer programming, Theoretical Computer Science, v.332 n.1-3, p.123-139, 28 February 2005
	Sung-woo Cho , Ashish Goel, Pricing for fairness: distributed resource allocation for multiple objectives, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Baruch Awerbuch , Rohit Khandekar, Distributed network monitoring and multicommodity flows: a primal-dual approach, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Baruch Awerbuch , Rohit Khandekar, Minimizing the total cost of network measurements in a distributed manner: a primal-dual approach, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Baruch Awerbuch , Rohit Khandekar , Satish Rao, Distributed algorithms for multicommodity flow problems via approximate steepest descent framework, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.949-957, January 07-09, 2007, New Orleans, Louisiana
	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
	Pavlos S. Efraimidis, The complexity of linear programming in (γ,κ)-form, Information Processing Letters, v.105 n.5, p.199-201, February, 2008
	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
	Alessandro Panconesi , Mauro Sozio, Fast distributed scheduling via primal-dual, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Niv Buchbinder , Joseph (Seffi) Naor, Online Primal-Dual Algorithms for Covering and Packing, Mathematics of Operations Research, v.34 n.2, p.270-286, May 2009
	Lance Fortnow , Russell Impagliazzo , Valentine Kabanets , Christopher Umans, On the Complexity of Succinct Zero-Sum Games, Computational Complexity, v.17 n.3, p.353-376, October 2008
	Niv Buchbinder , Joseph (Seffi) Naor, The Design of Competitive Online Algorithms via a Primal: Dual Approach, Foundations and Trends® in Theoretical Computer Science, v.3 n.2$#8211;3, p.93-263, February 2009
	Devavrat Shah, Gossip Algorithms, Foundations and Trends® in Networking, v.3 n.1, p.1-125, January 2009