{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T12:01:15Z","timestamp":1742385675917},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422877"},{"type":"electronic","value":"9783540482246"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_19","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T02:29:04Z","timestamp":1193538544000},"page":"225-236","source":"Crossref","is-referenced-by-count":18,"title":["Approximation Algorithms for Partial Covering Problems"],"prefix":"10.1007","author":[{"given":"Rajiv","family":"Gandhi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samir","family":"Khuller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"19_CR1","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s000390050062","volume":"8","author":"N. Alon","year":"1998","unstructured":"N. Alon, R. Boppana and J. H. Spencer. An asymptotic isoperimetric inequality. Geometric and Functional Analysis, 8:411\u2013436, 1998.","journal-title":"Geometric and Functional Analysis"},{"issue":"1","key":"19_CR2","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B. Baker","year":"1994","unstructured":"B. Baker. Approximation Algorithms for NP-Complete Problems on Planar Graphs. JACM, Vol 41 (1), (1994), pp. 153\u2013190.","journal-title":"JACM"},{"key":"19_CR3","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","volume":"2","author":"R. Bar-Yehuda","year":"1981","unstructured":"R. Bar-Yehuda and S. Even. A linear time approximation algorithm for the weighted vertex cover problem. J. of Algorithms 2:198\u2013203, 1981.","journal-title":"J. of Algorithms"},{"key":"19_CR4","first-page":"27","volume":"25","author":"R. Bar-Yehuda","year":"1985","unstructured":"R. Bar-Yehuda and S. Even. A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics, 25:27\u201345, 1985.","journal-title":"Annals of Discrete Mathematics"},{"unstructured":"R. Bar-Yehuda. Using homogeneous weights for approximating the partial cover problem. In Proc. Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 71\u201375, 1999.","key":"19_CR5"},{"doi-asserted-by":"crossref","unstructured":"N. Bshouty, and L. Burroughs. Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem. The Proceedings of the Fifteenth Annual Symposium on the Theoretical Aspects of Computer Science 298\u2013308, 1998.","key":"19_CR6","DOI":"10.1007\/BFb0028569"},{"unstructured":"M. Charikar, S. Khuller, D. Mount, and G. Narasimhan. Algorithms for Facility Location Problems with Outliers. In Proc. Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, 642\u2013651, 2001.","key":"19_CR7"},{"issue":"3","key":"19_CR8","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chv\u00e1tal","year":"1979","unstructured":"V. Chv\u00e1tal. A greedy heuristic for the set-covering problem. Math. of Oper. Res. Vol. 4, 3, 233\u2013235, 1979.","journal-title":"Math. of Oper. Res"},{"key":"19_CR9","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0020-0190(83)90007-8","volume":"16","author":"K. L. Clarkson","year":"1983","unstructured":"K. L. Clarkson. A modification of the greedy algorithm for the vertex cover. Information Processing Letters 16:23\u201325, 1983.","journal-title":"Information Processing Letters"},{"unstructured":"T. H. Cormen, C. E. Leiserson and R. L. Rivest, \u201cIntroduction to Algorithms\u201d, MIT Press, 1989.","key":"19_CR10"},{"doi-asserted-by":"crossref","unstructured":"R. Duh and M. F\u00fcrer. Approximating k-set cover by semi-local optimization. In Proc. 29th STOC, May 1997, pages 256\u2013264.","key":"19_CR11","DOI":"10.1145\/258533.258599"},{"doi-asserted-by":"crossref","unstructured":"R. Gandhi, S. Khuller and A. Srinivasan. Approximation algorithms for partial covering problems. Technical Report CS-TR-# 4234 (April 2001). Also available at: http:\/\/www.cs.umd.edu\/users\/samir\/grant\/icalp01.ps","key":"19_CR12","DOI":"10.1007\/3-540-48224-5_19"},{"key":"19_CR13","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0020-0190(93)90173-7","volume":"48","author":"O. Goldschmidt","year":"1993","unstructured":"O. Goldschmidt, D. Hochbaum, and G. Yu. A modified greedy heuristic for the set covering problem with improved worst case bound. Information Processing Letters 48(1993), 305\u2013310.","journal-title":"Information Processing Letters"},{"key":"19_CR14","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/S0895480195287541","volume":"11","author":"M. X. Goemans","year":"1998","unstructured":"M. X. Goemans and J. Kleinberg. The Lov\u00e1sz theta function and a semidefinite programming relaxation of vertex cover. SIAM Journal on Discrete Mathematics, 11:196\u2013204, 1998.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"19_CR15","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"M. X. Goemans","year":"1995","unstructured":"M. X. Goemans and D. P. Williamson. A general approximation technique for constrained forest problems. SIAM Journal on Computing, 24:296\u2013317, 1995.","journal-title":"SIAM Journal on Computing"},{"key":"19_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1007\/3-540-61310-2_10","volume-title":"Proc. Fifth Conference on Integer Programming and Combinatorial Optimization","author":"M. Halld\u00f3rsson","year":"1996","unstructured":"M. Halld\u00f3rsson. Approximating k-set cover and complementary graph coloring. In Proc. Fifth Conference on Integer Programming and Combinatorial Optimization, June 1996, LNCS 1084, pages 118\u2013131."},{"unstructured":"E. Halperin. Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. In Proc. Eleventh ACM-SIAM Symposium on Discrete Algorithms, January 2000, pages 329\u2013337.","key":"19_CR17"},{"doi-asserted-by":"crossref","unstructured":"D. S. Hochbaum. Approximation algorithms for the set covering and vertex cover problems. W.P.#64-79-80, GSIA, Carnegie-Mellon University, April 1980. Also: SIAM J. Comput. 11(3) 1982.","key":"19_CR18","DOI":"10.1137\/0211045"},{"key":"19_CR19","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"D. S. Hochbaum","year":"1983","unstructured":"D. S. Hochbaum. Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Applied Mathematics 6:243\u2013254, 1983.","journal-title":"Discrete Applied Mathematics"},{"unstructured":"D. S. Hochbaum (editor). Approximation Algorithms for NP-hard problems. PWS Publishing Company, 1996.","key":"19_CR20"},{"doi-asserted-by":"crossref","unstructured":"D. S. Hochbaum. The t-vertex cover problem: Extending the half integrality framework with budget constraints. In Proc. First International Workshop on Approximation Algorithms for Combinatorial Optimization Problems 111\u2013122, 1998.","key":"19_CR21","DOI":"10.1007\/BFb0053968"},{"issue":"1","key":"19_CR22","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"D. S. Hochbaum","year":"1985","unstructured":"D. S. Hochbaum and W. Maass. Approximation schemes for covering and packing problems in image processing and VLSI. Journal of ACM, 32(1):130\u2013136, 1985.","journal-title":"Journal of ACM"},{"key":"19_CR23","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D. S. Johnson","year":"1974","unstructured":"D. S. Johnson. Approximation algorithms for combinatorial problems. J. Comput. System Sci., 9:256\u2013278, 1974.","journal-title":"J. Comput. System Sci."},{"unstructured":"M. Kearns. The computational complexity of machine learning. M.I.T. Press, 1990.","key":"19_CR24"},{"issue":"2","key":"19_CR25","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.1994.1036","volume":"17","author":"S. Khuller","year":"1994","unstructured":"S. Khuller, U. Vishkin, and N. Young. A Primal Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Cover. Journal of Algorithms, 17(2):280\u2013289, 1994.","journal-title":"Journal of Algorithms"},{"key":"19_CR26","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e1sz","year":"1975","unstructured":"L. Lov\u00e1sz. On the ratio of optimal integral and fractional covers. Discrete Math. 13:383\u2013390, 1975.","journal-title":"Discrete Math."},{"key":"19_CR27","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G. L. Nemhauser","year":"1975","unstructured":"G. L. Nemhauser and L. E. Trotter, Jr. Vertex packings: Structural properties and algorithms. Mathematical Programming 8:232\u2013248, 1975.","journal-title":"Mathematical Programming"},{"key":"19_CR28","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01202286","volume":"4","author":"E. Petrank","year":"1994","unstructured":"E. Petrank. The hardness of approximation: Gap location. Computational Complexity 4:133\u2013157, 1994.","journal-title":"Computational Complexity"},{"key":"19_CR29","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0020-0190(97)00182-8","volume":"64","author":"P. Slav\u00edk","year":"1997","unstructured":"P. Slav\u00edk. Improved performance of the greedy algorithm for partial cover. Information Processing Letters 64:251\u2013254, 1997.","journal-title":"Information Processing Letters"},{"unstructured":"A. Srinivasan. New Approaches to Covering and Packing Problems. In Proc. Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, 567\u2013576, 2001.","key":"19_CR30"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,14]],"date-time":"2023-05-14T11:08:39Z","timestamp":1684062519000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_19","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}