Approximation schemes for covering and packing problems in image processing and VLSI

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximation schemes for covering and packing problems in image processing and VLSI

Full text

Pdf (592 KB)

Source

Journal of the ACM (JACM) archive
Volume 32 , Issue 1 (January 1985) table of contents

Pages: 130 - 136

Year of Publication: 1985

ISSN:0004-5411

Authors

Dorit S. Hochbaum	School of Business Administration, 350 Barrows Hall, University of California at Berkeley, Berkeley, CA
Wolfgang Maass	Department of Mathematics, University of Illinois, Chicago, IL

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 30, Downloads (12 Months): 269, Citation Count: 73

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

ABSTRACT

A unified and powerful approach is presented for devising polynomial approximation schemes for many strongly NP-complete problems. Such schemes consist of families of approximation algorithms for each desired performance bound on the relative error &egr; > &Ogr;, with running time that is polynomial when &egr; is fixed. Though the polynomiality of these algorithms depends on the degree of approximation &egr; being fixed, they cannot be improved, owing to a negative result stating that there are no fully polynomial approximation schemes for strongly NP-complete problems unless NP = P. The unified technique that is introduced here, referred to as the shifting strategy, is applicable to numerous geometric covering and packing problems. The method of using the technique and how it varies with problem parameters are illustrated. A similar technique, independently devised by B. S. Baker, was shown to be applicable for covering and packing problems on planar graphs.

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	BAKER, B. S.Approximation algorithms for NP-complete problems on planar graphs. In Proceed. ings of the 24th Annual IEEE Symposium on Foundations of Computer Science (Tucson, Ariz., Nov. 7-9). IEEE, New York, 1983, pp. 265-273.
	2	BERMAN, F. D., LEIGHTON, F. T., AND SNYDER, L.Optimal tile salvage. Unpublished manuscript, 1982.
	3	FOWLER, R. J., PATERSON, M. S., AND TANIMOTO, S. L.Optimal packing and covering in the plane are NP-complete. Inf. Proc. Lett. 12, 3 (June 1981), 133-137.
	4	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
	5	HOCHBAUM, D. S., AND MAASS, W.Fast approximation schemes for geometric coveting and packing problems in robotics and VLSI. Unpublished manuscript, University of California, Berkeley, Calif., 1983.
	6	JOHNSON, D. S."File NP-completeness column: An ongoing guide. ~ Algorithms 3, 2 (June 1982), 182-195.
	7	TANIMOTO, S. L., AND FOWLER, R. J.Covering image subsets with patches. In Proceedings of the 5th International Conference on Pattern Recognition, 1980, pp. 835-839.

CITED BY 73

	Gruia Călinescu , Ion Măndoiu , Peng-Jun Wan , Alexander Zelikovsky, Selecting forwarding neighbors in wireless Ad Hoc networks, Proceedings of the 5th international workshop on Discrete algorithms and methods for mobile computing and communications, p.34-43, July 2001, Rome, Italy
	Moses Charikar , Chandra Chekuri , Tomás Feder , Rajeev Motwani, Incremental clustering and dynamic information retrieval, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.626-635, May 04-06, 1997, El Paso, Texas, United States
	Sanjeev Khanna , S. Muthukrishnan , Mike Paterson, On approximating rectangle tiling and packing, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.384-393, January 25-27, 1998, San Francisco, California, United States
	Hai Huang , Andréa W. Richa , Michael Segal, Approximation algorithms for the mobile piercing set problem with applications to clustering in ad-hoc networks, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA
	Harry B. Hunt, III , Madhav V. Marathe , Venkatesh Radhakrishnan , S. S. Ravi , Daniel J. Rosenkrantz , Richard E. Stearns, Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems, Information and Computation, v.173 n.1, p.40-63, February 25, 2002
	Xiang-Yang Li , Yu Wang, Simple heuristics and PTASs for intersection graphs in wireless ad hoc networks, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA
	Thomas Erlebach , Klaus Jansen , Eike Seidel, Polynomial-time approximation schemes for geometric graphs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.671-679, January 07-09, 2001, Washington, D.C., United States
	Liang Chen , Naoyuki Tokuda, Robustness of regional matching scheme over global matching scheme, Artificial Intelligence, v.144 n.1-2, p.213-232, March 2003
	Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998
	Yigal Bejerano, Efficient integration of multi-hop wireless and wired networks with QoS constraints, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA
	Matthias Galota , Christian Glaßer , Steffen Reith , Heribert Vollmer, A polynomial-time approximation scheme for base station positioning in UMTS networks, Proceedings of the 5th international workshop on Discrete algorithms and methods for mobile computing and communications, p.52-59, July 2001, Rome, Italy
	Srinivas Doddi , Madhav V. Marathe , Andy Mirzaian , Bernard M. E. Moret , Binhai Zhu, Map labeling and its generalizations, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.148-157, January 05-07, 1997, New Orleans, Louisiana, United States
	Marc van Kreveld , Tycho Strijk , Alexander Wolff, Point set labeling with sliding labels, Proceedings of the fourteenth annual symposium on Computational geometry, p.337-346, June 07-10, 1998, Minneapolis, Minnesota, United States
	Franz Aurenhammer , Naoki Katoh , Hiromichi Kojima , Makoto Ohsaki , Yinfeng Xu, Approximating uniform triangular meshes in polygons, Theoretical Computer Science, v.289 n.2, p.879-895, 30 October 2002
	Hervé Brönnimann , Michael T. Goodrich, Almost optimal set covers in finite VC-dimension: (preliminary version), Proceedings of the tenth annual symposium on Computational geometry, p.293-302, June 06-08, 1994, Stony Brook, New York, United States
	Domenico Cantone , Alfredo Ferro , Alfredo Pulvirenti , Diego Reforgiato Recupero , Dennis Shasha, Antipole Tree Indexing to Support Range Search and K-Nearest Neighbor Search in Metric Spaces, IEEE Transactions on Knowledge and Data Engineering, v.17 n.4, p.535-550, April 2005
	Sergio Cabello , Marc van Kreveld, Approximation algorithms for aligning points, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Timothy M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, Journal of Algorithms, v.46 n.2, p.178-189, February 2003
	Klaus Jansen , Guochaun Zhang, On rectangle packing: maximizing benefits, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Tetsuo Asano , Naoki Katoh , Hisao Tamaki , Takeshi Tokuyama, Covering points in the plane by k-tours: towards a polynomial time approximation scheme for general k, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.275-283, May 04-06, 1997, El Paso, Texas, United States
	Jie Gao , Leonidas Guibas , John Hershberger , Li Zhang , An Zhu, Discrete mobile centers, Proceedings of the seventeenth annual symposium on Computational geometry, p.188-196, June 2001, Medford, Massachusetts, United States
	Danny Z. Chen , Xiaobo Hu , Yingping Huang , Yifan Li , Jinhui Xu, Algorithms for congruent sphere packing and applications, Proceedings of the seventeenth annual symposium on Computational geometry, p.212-221, June 2001, Medford, Massachusetts, United States
	John Hershberger, Smooth kinetic maintenance of clusters, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Piotr Berman , Bhaskar DasGupta , S. Muthukrishnan, Slice and dice: a simple, improved approximate tiling recipe, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.455-464, January 06-08, 2002, San Francisco, California
	Massimo Franceschetti , Matthew Cook , Jehoshua Bruck, A Geometric Theorem for Network Design, IEEE Transactions on Computers, v.53 n.4, p.483-489, April 2004
	Yigal Bejerano, Efficient integration of multihop wireless and wired networks with QoS constraints, IEEE/ACM Transactions on Networking (TON), v.12 n.6, p.1064-1078, December 2004
	Rajiv Gandhi , Samir Khuller , Aravind Srinivasan, Approximation algorithms for partial covering problems, Journal of Algorithms, v.53 n.1, p.55-84, October 2004
	Hai Huang , Andréa W. Richa , Michael Segal, Approximation algorithms for the mobile piercing set problem with applications to clustering in ad-hoc networks, Mobile Networks and Applications, v.9 n.2, p.151-161, April 2004
	Gruia Călinescu , Ion I. Mandoiu , Peng-Jun Wan , Alexander Z. Zelikovsky, Selecting forwarding neighbors in wireless ad hoc networks, Mobile Networks and Applications, v.9 n.2, p.101-111, April 2004
	Friedrich Eisenbrand , Stefan Funke , Andreas Karrenbauer , Joachim Reichel , Elmar Schömer, Packing a trunk: now with a twist!, Proceedings of the 2005 ACM symposium on Solid and physical modeling, p.197-206, June 13-15, 2005, Cambridge, Massachusetts
	De-fu Zhang , An-sheng Deng, An effective hybrid algorithm for the problem of packing circles into a larger containing circle, Computers and Operations Research, v.32 n.8, p.1941-1951, August 2005
	Nissan Lev-Tov , David Peleg, Polynomial time approximation schemes for base station coverage with minimum total radii, Computer Networks and ISDN Systems, v.47 n.4, p.489-501, 15 March 2005
	John Hershberger, Smooth kinetic maintenance of clusters, Computational Geometry: Theory and Applications, v.31 n.1-2, p.3-30, May 2005
	Christian Glaßer , Steffen Reith , Heribert Vollmer, The complexity of base station positioning in cellular networks, Discrete Applied Mathematics, v.148 n.1, p.1-12, 30 April 2005
	Kenneth L. Clarkson , Kasturi Varadarajan, Improved approximation algorithms for geometric set cover, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Miroslav Chlebík , Janka Chlebíková, Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Fabian Kuhn , Tim Nieberg , Thomas Moscibroda , Roger Wattenhofer, Local approximation schemes for ad hoc and sensor networks, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany
	Rajagopal Iyengar , Koushik Kar , Suman Banerjee, Low-coordination topologies for redundancy in sensor networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA
	Carlos Guestrin , Andreas Krause , Ajit Paul Singh, Near-optimal sensor placements in Gaussian processes, Proceedings of the 22nd international conference on Machine learning, p.265-272, August 07-11, 2005, Bonn, Germany
	Wen Qi Huang , Yu Li , Chu Min Li , Ru Chu Xu, New heuristics for packing unequal circles into a circular container, Computers and Operations Research, v.33 n.8, p.2125-2142, August 2006
	Defu Zhang , Yan Kang , Ansheng Deng, A new heuristic recursive algorithm for the strip rectangular packing problem, Computers and Operations Research, v.33 n.8, p.2209-2217, August 2006
	Xiang-Yang Li , Yu Wang, Simple approximation algorithms and PTASs for various problems in wireless ad hoc networks, Journal of Parallel and Distributed Computing, v.66 n.4, p.515-530, April 2006
	Frank Nielsen, On point covers of c-oriented polygons, Theoretical Computer Science, v.263 n.1-2, p.17-29, July 28 2001
	Dezun Dong , Yunhao Liu , Xiangke Liao, Self-monitoring for sensor networks, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, May 26-30, 2008, Hong Kong, Hong Kong, China
	Adam H. Cannon , Lenore J. Cowen, Approximation Algorithms for the Class Cover Problem, Annals of Mathematics and Artificial Intelligence, v.40 n.3-4, p.215-223, March 2004
	Helmut Alt , Esther M. Arkin , Hervé Brönnimann , Jeff Erickson , Sándor P. Fekete , Christian Knauer , Jonathan Lenchner , Joseph S. B. Mitchell , Kim Whittlesey, Minimum-cost coverage of point sets by disks, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Yigal Bejerano , Randeep S. Bhatia, MiFi: a framework for fairness and QoS assurance for current IEEE 802.11 networks with multiple access points, IEEE/ACM Transactions on Networking (TON), v.14 n.4, p.849-862, August 2006
	Gaurav Sharma , Ravi R. Mazumdar , Ness B. Shroff, On the complexity of scheduling in wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA
	Anand Srinivas , Gil Zussman , Eytan Modiano, Mobile backbone networks --: construction and maintenance, Proceedings of the seventh ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy
	Stefan Funke , Alex Kesselman , Fabian Kuhn , Zvi Lotker , Michael Segal, Improved approximation algorithms for connected sensor cover, Wireless Networks, v.13 n.2, p.153-164, April 2007
	Piotr Berman , Bhaskar DasGupta , Dhruv Mubayi , Robert Sloan , György Turán , Yi Zhang, The inverse protein folding problem on 2D and 3D lattices, Discrete Applied Mathematics, v.155 n.6-7, p.719-732, April, 2007
	Yaodong Cui , Yuli Yang , Xian Cheng , Peihua Song, A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem, Computers and Operations Research, v.35 n.4, p.1281-1291, April, 2008
	Piotr Berman , Jieun Jeong , Shiva Prasad Kasiviswanathan , Bhuvan Urgaonkar, Packing to angles and sectors, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Jacob Fox , János Pach, Coloring k_k-free intersection graphs of geometric objects in the plane, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	Mao Chen , Wenqi Huang, A two-level search algorithm for 2D rectangular packing problem, Computers and Industrial Engineering, v.53 n.1, p.123-136, August, 2007
	Donghui Chen , Ding-Zhu Du , Xiao-Dong Hu , Guo-Hui Lin , Lusheng Wang , Guoliang Xue, Approximations for Steiner Trees with Minimum Number of Steiner Points, Journal of Global Optimization, v.18 n.1, p.17-33, September 2000
	Yi Ouyang , Yurong Xu , Zhengyi Le , Guanling Chen , Fillia Makedon, Providing location privacy in assisted living environments, Proceedings of the 1st international conference on PErvasive Technologies Related to Assistive Environments, July 16-18, 2008, Athens, Greece
	Ken Been , Martin Nöllenburg , Sheung-Hung Poon , Alexander Wolff, Optimizing active ranges for consistent dynamic map labeling, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	Thomas Erlebach , Erik Jan van Leeuwen, Approximating geometric coverage problems, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1267-1276, January 20-22, 2008, San Francisco, California
	Tiziana Calamoneri , Andrea E. F. Clementi , Miriam Di Ianni , Massimo Lauria , Angelo Monti , Riccardo Silvestri, Minimum-Energy Broadcast and disk cover in grid wireless networks, Theoretical Computer Science, v.399 n.1-2, p.38-53, June, 2008
	Zhipeng Lü , Wenqi Huang, PERM for solving circle packing problem, Computers and Operations Research, v.35 n.5, p.1742-1755, May, 2008
	Paz Carmi , Matthew J. Katz , Nissan Lev-Tov, Polynomial-time approximation schemes for piercing and covering with applications in wireless networks, Computational Geometry: Theory and Applications, v.39 n.3, p.209-218, April, 2008
	Errol L. Lloyd , Guoliang Xue, Relay Node Placement in Wireless Sensor Networks, IEEE Transactions on Computers, v.56 n.1, p.134-138, January 2007
	Andreas Krause , Ajit Singh , Carlos Guestrin, Near-Optimal Sensor Placements in Gaussian Processes: Theory, Efficient Algorithms and Empirical Studies, The Journal of Machine Learning Research, 9, p.235-284, 6/1/2008
	Ralf Klasing , Nelson Morales , Stéphane Pérennes, On the complexity of bandwidth allocation in radio networks, Theoretical Computer Science, v.406 n.3, p.225-239, October, 2008
	Parinya Chalermsook , Julia Chuzhoy, Maximum independent set of rectangles, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.892-901, January 04-06, 2009, New York, New York
	Peng-Jun Wan, Multiflows in multihop wireless networks, Proceedings of the tenth ACM international symposium on Mobile ad hoc networking and computing, May 18-21, 2009, New Orleans, LA, USA
	Pankaj K. Agarwal , Esther Ezra , Micha Shair, Near-linear approximation algorithms for geometric hitting sets, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	Eyal Ackerman , Jacob Fox , János Pach , Andrew Suk, On grids in topological graphs, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	Anand Srinivas , Gil Zussman , Eytan Modiano, Construction and Maintenance of Wireless Mobile Backbone Networks, IEEE/ACM Transactions on Networking (TON), v.17 n.1, p.239-252, February 2009
	Shimon Abravaya , Michael Segal, Maximizing the number of obnoxious facilities to locate within a bounded region, Computers and Operations Research, v.37 n.1, p.163-171, January, 2010
	Patrik Floréen , Joel Kaasinen , Petteri Kaski , Jukka Suomela, An optimal local approximation algorithm for max-min linear programs, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada
	Andreas Krause , Ram Rajagopal , Anupam Gupta , Carlos Guestrin, Simultaneous placement and scheduling of sensors, Proceedings of the 2009 International Conference on Information Processing in Sensor Networks, p.181-192, April 13-16, 2009