{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:44:50Z","timestamp":1725551090000},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540003311"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/3-540-36379-3_23","type":"book-chapter","created":{"date-parts":[[2010,3,29]],"date-time":"2010-03-29T17:12:05Z","timestamp":1269882725000},"page":"258-269","source":"Crossref","is-referenced-by-count":1,"title":["Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP"],"prefix":"10.1007","author":[{"given":"Edith","family":"Hemaspaandra","sequence":"first","affiliation":[]},{"given":"J\u00f6rg","family":"Rothe","sequence":"additional","affiliation":[]},{"given":"Holger","family":"Spakowski","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"23_CR1","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/S0020-0190(96)00208-6","volume":"61","author":"H. Bodlaender","year":"1997","unstructured":"H. Bodlaender, D. Thilikos, and K. Yamazaki. It is hard to know when greedy is good for finding independent sets. Information Processing Letters, 61:101\u2013106, 1997.","journal-title":"Information Processing Letters"},{"issue":"1\/2","key":"23_CR2","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/S0747-7171(89)80025-2","volume":"8","author":"M. Clausen","year":"1989","unstructured":"M. Clausen and A. Fortenbacher. Efficient solution of linear diophantine equations. Journal of Symbolic Computation, 8(1\/2):201\u2013216, 1989.","journal-title":"Journal of Symbolic Computation"},{"issue":"3","key":"23_CR3","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. Mathematics of Operations Research, 4(3):233\u2013235, 1979.","journal-title":"Mathematics of Operations Research"},{"issue":"4","key":"23_CR4","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634\u2013652, July 1998.","journal-title":"Journal of the ACM"},{"unstructured":"M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, 1979.","key":"23_CR5"},{"issue":"3","key":"23_CR6","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0022-0000(89)90025-1","volume":"39","author":"L. Hemachandra","year":"1989","unstructured":"L. Hemachandra. The strong exponential hierarchy collapses. Journal of Computer and System Sciences, 39(3):299\u2013322, 1989.","journal-title":"Journal of Computer and System Sciences"},{"issue":"6","key":"23_CR7","doi-asserted-by":"publisher","first-page":"806","DOI":"10.1145\/268999.269002","volume":"44","author":"E. Hemaspaandra","year":"1997","unstructured":"E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. Exact analysis of Dodgson elections: Lewis Carroll\u2019s 1876 voting system is complete for parallel access to NP. Journal of the ACM, 44(6):806\u2013825, 1997.","journal-title":"Journal of the ACM"},{"issue":"3","key":"23_CR8","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/S0020-0190(97)00219-6","volume":"65","author":"E. Hemaspaandra","year":"1998","unstructured":"E. Hemaspaandra and J. Rothe. Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP. Information Processing Letters, 65(3):151\u2013156, February 1998.","journal-title":"Information Processing Letters"},{"unstructured":"E. Hemaspaandra, J. Rothe, and H. Spakowski. Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP. Technical Report cs.CC\/0110025, Computing Research Repository (CoRR), October 2001. 16 pages. Available on-line at \n                  http:\/\/xxx.lanl.gov\/abs\/cs.CC\/0110025\n                  \n                .","key":"23_CR9"},{"issue":"3","key":"23_CR10","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D. Johnson","year":"1974","unstructured":"D. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9(3):256\u2013278, 1974.","journal-title":"Journal of Computer and System Sciences"},{"key":"23_CR11","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M. Krentel","year":"1988","unstructured":"M. Krentel. The complexity of optimization problems. Journal of Computer and System Sciences, 36:490\u2013509, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"23_CR12","first-page":"419","volume":"21","author":"J. K\u00f6bler","year":"1987","unstructured":"J. K\u00f6bler, U. Sch\u00f6ning, and K. Wagner. The difference and truth-table hierarchies for NP. R.A.I.R.O. Informatique th\u00e9orique et Applications, 21:419\u2013435, 1987.","journal-title":"R.A.I.R.O. Informatique th\u00e9orique et Applications"},{"key":"23_CR13","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 Mathematics, 13:383\u2013390, 1975.","journal-title":"Discrete Mathematics"},{"issue":"5","key":"23_CR14","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. Journal of the ACM, 41(5):960\u2013981, September 1994.","journal-title":"Journal of the ACM"},{"unstructured":"C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.","key":"23_CR15"},{"unstructured":"C. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, 1982.","key":"23_CR16"},{"key":"23_CR17","series-title":"Lect Notes Comput Sci","first-page":"269","volume-title":"Two remarks on the power of counting","author":"C. Papadimitriou","year":"1983","unstructured":"C. Papadimitriou and S. Zachos. Two remarks on the power of counting. In Proceedings of the 6th GI Conference on Theoretical Computer Science, pages 269\u2013276. Springer-Verlag Lecture Notes in Computer Science #145, 1983."},{"key":"23_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1007\/3-540-44450-5_28","volume-title":"A classical approach for new results","author":"H. Spakowski","year":"2000","unstructured":"H. Spakowski and J. Vogel. \u00f8p\n                        2-completeness: A classical approach for new results. In Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science, pages 348\u2013360. Springer-Verlag Lecture Notes in Computer Science #1974, December 2000."},{"key":"23_CR19","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0304-3975(87)90049-1","volume":"51","author":"K. Wagner","year":"1987","unstructured":"K. Wagner. More complicated questions about maxima and minima, and some closures of NP. Theoretical Computer Science, 51:53\u201380, 1987.","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"23_CR20","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"K. Wagner","year":"1990","unstructured":"K. Wagner. Bounded query classes. SIAM Journal on Computing, 19(5):833\u2013846, 1990.","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","deposited":{"date-parts":[[2019,2,25]],"date-time":"2019-02-25T02:57:33Z","timestamp":1551063453000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36379-3_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540003311"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-36379-3_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}