e-approximations with minimum packing constraint violation (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

e-approximations with minimum packing constraint violation (extended abstract)

Full text

Pdf (1.08 MB)

Source

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

Victoria, British Columbia, Canada

Pages: 771 - 782

Year of Publication: 1992

ISBN:0-89791-511-9

Authors

Jyh-Han Lin	Department of Computer Science, Brown University, Providence, R. I.
Jeffrey Scott Vitter	Department of Computer Science, Brown University, Providence, R. I.

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 64, Citation Count: 52

Additional Information:

abstract 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/129712.129787 What is a DOI?

ABSTRACT

We present efficient new randomized and deterministic methods for transforming optimal solutions for a type of relaxed integer linear program into provably good solutions for the corresponding NP-hard discrete optimization problem. Without any constraint violation, the &egr;-approximation problem for many problems of this type is itself NP-hard. Our methods provide polynomial-time &egr;-approximations while attempting to minimize the packing constraint violation. Our methods lead to the first known approximation algorithms with provable performance guarantees for the s-median problem, the tree prunning problem, and the generalized assignment problem. These important problems have numerous applications to data compression, vector quantization, memory-based learning, computer graphics, image processing, clustering, regression, network location, scheduling, and communication. We provide evidence via reductions that our approximation algorithms are nearly optimal in terms of the packing constraint violation. We also discuss some recent applications of our techniques to scheduling problems.

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.

	ACC	Sang Ahn , Colin Cooper , Gerard Cornuejols , Alan Frieze, Probabilistic analysis of a relaxation for the k-median problem, Mathematics of Operations Research, v.13 n.1, p.1-31, February 1988 [doi>10.1287/moor.13.1.1]
	BFO	L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone, Classification Trees and Regression Trees, Wadsworth, Belmont, CA, 1984.
	CLG	P. A. Chou, T. Lookabaugh, and R.. M. Gray, "Optimal Pruning with Applications to Tree-Structured Source Coding and Modeling," IEEE Transactions on Information Theory (1989), 299-315.
	Chv	V. Chv~tal, "A Greedy Heuristic for the Set- Covering Problem," Mathematics of Operalions Research 4(1979), 233-235.
	FeG	Tomás Feder , Daniel Greene, Optimal algorithms for approximate clustering, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.434-444, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62255]
	FiH	M. L. Fisher and D. S. Hochbaum, "Probabilistic Analysis of the Planar K-Median Problem," Mathematics of Operations Research 5 (February 1980), 27-34.
	GaJ	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	Gon	T. F. Gonzalez, "Clustering to Minimize the Maximum Interc}uster Distance," Theoretical Computer Science 38(1985), 293-306.
	GLS	M. GrStschel, L. Lov~sz, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, Berlin, Heidelberg, New York, 1988.
	Hoc	D. S. Hochbaum, "Heuristics for the Fixed- Cost Median Problem," Mathematical Programming 22 (1982), 148-162.
	HoSa	Dorit S. Hochbaum , David B. Shmoys, Using dual approximation algorithms for scheduling problems theoretical and practical results, Journal of the ACM (JACM), v.34 n.1, p.144-162, Jan. 1987 [doi>10.1145/7531.7535]
	HoSb	Dorit S. Hochbaum , David B. Shmoys, A unified approach to approximation algorithms for bottleneck problems, Journal of the ACM (JACM), v.33 n.3, p.533-550, July 1986 [doi>10.1145/5925.5933]
	Joh	D. S. Johnson, "Approximation Algorithms for Combinatorial Problems," Journal of Computer and System Sciences 9 (1974), 256-278.
	KaH	O. Kariv and S, L. Hakimi, "An Algorithmic Approach to Network Location Problems. Ii: The p-Medlans," #qlAM Journal on Applied Mathematics (1979), 539-560.
	Kar	N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
	Kha	L. G. Khachiyan, "A Polynomial Algorithm in Linear Programming," Soviet Math. Doklady 20 (1979), 191-194.
	Kuh	It. W. Kuhn, "The Hungarian Method for the Assignment Problem," Naval Research Logistics Quarterly 2 (1955), 83-97.
	LaL	E. L. Lawler , J. Labetoulle, On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming, Journal of the ACM (JACM), v.25 n.4, p.612-619, Oct. 1978 [doi>10.1145/322092.322101]
	LST	J. K. Lenstra , D. B. Shmoys , É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming: Series A and B, v.46 n.3, p.259-271, Apr. 1990 [doi>10.1007/BF01585745]
	LSC	J. Lin, J. A. Storer, and M. Cohn, "On the Complexity of Optimal Tree Pruning for Source Coding," in Proceedings of the Data Compression Conference, J. A. Storer and J. H. Reif, eds., Snowbird, Utah, April 1991, 63- 72.
	LiVa	Jyh Lin , Jeffrey S Vitter, A Theory for Memory-Based Learning, Brown University, Providence, RI, 1992
	LiVb	J.-H. Lin and J. S. Vitter, "Nearly Optimal Vector Quantization via Linear Programming," in Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, March 1992.
	Lov	L. Lovdsz, "On the Ratio of Optimal Integral and Fractional Covers," Discrete Malhemalics 13 (1975), 383-390.
	MeS	N. Megiddo and K. J. Supowit, "On the Complexity of Some Common Geometric Location Problems," SIAM Journal on Computing 13 (1984), 182-196.
	Pap	C. H. Papadimitriou, "Worst-case and Probabilistic Analysis of a Geometric Location Problem," SIAM Journal on Computing 10(1981), 542-557.
	Rag	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]
	RaT	Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
	SaG	Sartaj Sahni , Teofilo Gonzalez, P-Complete Approximation Problems, Journal of the ACM (JACM), v.23 n.3, p.555-565, July 1976 [doi>10.1145/321958.321975]
	ShT	D. B. Shmoys and t#. Tardos, Personal Communication, january 23, 1992.

CITED BY 52

	David B. Shmoys, Approximation algorithms for clustering problems, Proceedings of the twelfth annual conference on Computational learning theory, p.100-101, July 07-09, 1999, Santa Cruz, California, United States
	Madhukar R. Korupolu , C. Greg Plaxton , Rajmohan Rajaraman, Analysis of a local search heuristic for facility location problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.1-10, January 25-27, 1998, San Francisco, California, United States
	Sanjeev Arora , Prabhakar Raghavan , Satish Rao, Approximation schemes for Euclidean k-medians and related problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.106-113, May 24-26, 1998, Dallas, Texas, United States
	Moses Charikar , Sudipto Guha , Éva Tardos , David B. Shmoys, A constant-factor approximation algorithm for the k-median problem (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.1-10, May 01-04, 1999, Atlanta, Georgia, United States
	Adam Meyerson , Kamesh Munagala , Serge Plotkin, Web caching using access statistics, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.354-363, January 07-09, 2001, Washington, D.C., United States
	Leslie A. Hall , David B. Shmoys , Joel Wein, Scheduling to minimize average completion time: off-line and on-line algorithms, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.142-151, January 28-30, 1996, Atlanta, Georgia, United States
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	Aravind Srinivasan , Chung-Piaw Teo, A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.636-643, May 04-06, 1997, El Paso, Texas, United States
	R. Ravi , M. V. Marathe , S. S. Ravi , D. J. Rosenkrantz , H. B. Hunt, III, Many birds with one stone: multi-objective approximation algorithms, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.438-447, May 16-18, 1993, San Diego, California, United States
	Kamal Jain , Vijay V. Vazirani, Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation, Journal of the ACM (JACM), v.48 n.2, p.274-296, March 2001
	Neal E. Young, K-medians, facility location, and the Chernoff-Wald bound, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.86-95, January 09-11, 2000, San Francisco, California, United States
	Sudipto Guha , Kamesh Munagala, Improved algorithms for the data placement problem, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.106-107, January 06-08, 2002, San Francisco, California
	H. Noltemeier , H.-C. Wirth , S. O. Krumke, Network design and improvement, ACM Computing Surveys (CSUR), v.31 n.3es, Sept. 1999
	David B. Shmoys , Éva Tardos , Karen Aardal, Approximation algorithms for facility location problems (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.265-274, May 04-06, 1997, El Paso, Texas, United States
	Matthew Andrews , Lisa Zhang, Packet routing with arbitrary end-to-end delay requirements, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.557-565, May 01-04, 1999, Atlanta, Georgia, United States
	Sudipto Guha , Adam Meyerson , Kamesh Munagala, Improved algorithms for fault tolerant facility location, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.636-641, January 07-09, 2001, Washington, D.C., United States
	Jyh-Han Lin , Jeffrey Scott Vitter, A theory for memory-based learning, Proceedings of the fifth annual workshop on Computational learning theory, p.103-115, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha, Rounding via trees: deterministic approximation algorithms for group Steiner trees and k-median, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.114-123, May 24-26, 1998, Dallas, Texas, United States
	Fabián A. Chudak , David B. Shmoys, Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.581-590, January 05-07, 1997, New Orleans, Louisiana, United States
	Amit Kumar , Rajeev Rastogi , Avi Silberschatz , Bulent Yener, Algorithms for provisioning virtual private networks in the hose model, ACM SIGCOMM Computer Communication Review, v.31 n.4, p.135-146, October 2001
	Amit Kumar , Rajeev Rastogi , Avi Silberschatz , Bulent Yener, Algorithms for provisioning virtual private networks in the hose model, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.565-578, August 2002
	Chandra Chekuri , Sanjeev Khanna, A PTAS for the multiple knapsack problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.213-222, January 09-11, 2000, San Francisco, California, United States
	David B. Shmoys , Éva Tardos, Scheduling unrelated machines with costs, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.448-454, January 25-27, 1993, Austin, Texas, United States
	C. Heeren , H. V. Jagadish , L. Pitt, Optimal indexing using near-minimal space, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.244-251, June 09-11, 2003, San Diego, California
	Moses Charikar , Liadan O'Callaghan , Rina Panigrahy, Better streaming algorithms for clustering problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Chaitanya Swamy , David B. Shmoys, Fault-tolerant facility location, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	R. Ravi , A. Sinha, Multicommodity facility location, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Klaus Jansen , Lorant Porkolab, Improved approximation schemes for scheduling unrelated parallel machines, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.408-417, May 01-04, 1999, Atlanta, Georgia, United States
	Anupam Gupta , Jon Kleinberg , Amit Kumar , Rajeev Rastogi , Bulent Yener, Provisioning a virtual private network: a network design problem for multicommodity flow, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.389-398, July 2001, Hersonissos, Greece
	Adam Meyerson, Profit-earning facility location, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.30-36, July 2001, Hersonissos, Greece
	Moses Charikar , Sudipto Guha , Éva Tardos , David B. Shmoys, A constant-factor approximation algorithm for the k-median problem, Journal of Computer and System Sciences, v.65 n.1, p.129-149, August 2002
	Piotr Indyk, Sublinear time algorithms for metric space problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.428-434, May 01-04, 1999, Atlanta, Georgia, United States
	David Cohn , Eve A. Riskin , Richard Ladner, Theory and Practice of Vector Quantizers Trained on Small Training Sets, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.16 n.1, p.54-65, January 1994
	David B. Shmoys , Chaitanya Swamy , Retsef Levi, Facility location with Service Installation Costs, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Sudipto Guha , Adam Meyerson , Nina Mishra , Rajeev Motwani , Liadan O'Callaghan, Clustering Data Streams: Theory and Practice, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.515-528, March 2003
	Adam Meyerson , Liadan O'Callaghan , Serge Plotkin, A k-Median Algorithm with Running Time Independent of Data Size, Machine Learning, v.56 n.1-3, p.61-87
	Julia Chuzhoy , Yuval Rabani, Approximating k-median with non-uniform capacities, 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
	Sudipto Guha , Adam Meyerson , Kamesh Munagala, A constant factor approximation algorithm for the fault-tolerant facility location problem, Journal of Algorithms, v.48 n.2, p.429-440, September 2003
	Guang Xu , Jinhui Xu, An LP rounding algorithm for approximating uncapacitated facility location problem with penalties, Information Processing Letters, v.94 n.3, p.119-123, 16 May 2005
	Pavlos S. Efraimidis , Paul G. Spirakis, Weighted random sampling with a reservoir, Information Processing Letters, v.97 n.5, p.181-185, 16 March 2006
	Surajit Chaudhuri , Ashish Kumar Gupta , Vivek Narasayya, Compressing SQL workloads, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
	Igal Galperin, Analysis of greedy expert hiring and an application to memory-based learning (extended abstract), Proceedings of the ninth annual conference on Computational learning theory, p.217-223, June 28-July 01, 1996, Desenzano del Garda, Italy
	Roee Engelberg , Jochen Könemann , Stefano Leonardi , Joseph (Seffi) Naor, Cut problems in graphs with a budget constraint, Journal of Discrete Algorithms, v.5 n.2, p.262-279, June, 2007
	Jian-Jia Chen , Tei-Wei Kuo, Allocation cost minimization for periodic hard real-time tasks in energy-constrained DVS systems, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	Ke Chen, A constant factor approximation algorithm for k-median clustering with outliers, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.826-835, January 20-22, 2008, San Francisco, California
	Chaitanya Swamy , David B. Shmoys, Fault-tolerant facility location, ACM Transactions on Algorithms (TALG), v.4 n.4, p.1-27, August 2008
	Gaurav Sharma , Ravi R. Mazumdar, A case for hybrid sensor networks, IEEE/ACM Transactions on Networking (TON), v.16 n.5, p.1121-1132, October 2008
	MohammadHossein Bateni , MohammadTaghi Hajiaghayi, Assignment problem in content distribution networks: unsplittable hard-capacitated facility location, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.805-814, January 04-06, 2009, New York, New York
	Reuven Cohen , Gabi Nakibly, A traffic engineering approach for placement and selection of network services, IEEE/ACM Transactions on Networking (TON), v.17 n.2, p.487-500, April 2009
	Erez Kantor , David Peleg, Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems, Journal of Discrete Algorithms, v.7 n.3, p.341-362, September, 2009
	Saurav Pandit , Sriram Pemmaraju, Return of the primal-dual: distributed metric facilitylocation, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada