{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T09:18:54Z","timestamp":1737105534657,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540679967"},{"type":"electronic","value":"9783540444367"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44436-x_2","type":"book-chapter","created":{"date-parts":[[2007,6,18]],"date-time":"2007-06-18T09:33:14Z","timestamp":1182159194000},"page":"2-12","source":"Crossref","is-referenced-by-count":3,"title":["Instant Recognition of Polynomial Time Solvability, Half Integrality, and 2-Approximations"],"prefix":"10.1007","author":[{"given":"Dorit S.","family":"Hochbaum","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,3]]},"reference":[{"key":"2_CR1","unstructured":"M. Ball. Locating Competitive new facilities in the presence of existing facilities. Proceeding of the 5th United States Postal service Advanced Technology Conference 1169-1177, 1992."},{"key":"2_CR2","unstructured":"M. Bellare, O. Goldreich and M. Sudan. Free bits and nonapproximability. Proceedings of the 36 th Annual IEEE Symposium on Foundations of Computer Science (FOCS95). 422\u2013431, 1995."},{"issue":"5","key":"2_CR3","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0167-6377(99)00056-5","volume":"25","author":"F. Chudak","year":"1999","unstructured":"F. Chudak and D.S. Hochbaum. A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine. Operations Research Letters, 25:5 Dec 1999, 199\u2013204.","journal-title":"Operations Research Letters"},{"issue":"6","key":"2_CR4","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"M.X. Goemans and D.P. Williamson. Improved approximation algorithms for maximum c t and satisfiability problems sing semide finite programming. Journal of the ACM 42(6):1115\u20131145, November 1995.","journal-title":"Journal of the ACM"},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"A.V. Goldberg","year":"1988","unstructured":"A.V. Goldberg and R.E. Tarjan. A new approach to the maximum flow problem. J. of ACM 35, 921\u2013940, 1988.","journal-title":"J. of ACM"},{"key":"2_CR6","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/BF01585160","volume":"62","author":"D.S. Hochbaum","year":"1993","unstructured":"D.S. Hochbaum, N. Megiddo, J. Naor and A. Tamir. Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality. Mathematical Programming 62, 69\u201383, 1993.","journal-title":"Mathematical Programming"},{"issue":"4","key":"2_CR7","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1093\/forestscience\/43.4.544","volume":"43","author":"D.S. Hochbaum","year":"1997","unstructured":"D.S. Hochbaum and A. Pathria. Forest Harvesting and Minim m Cuts. Forest Science 43(4), Nov. 1997, 544\u2013554.","journal-title":"Forest Science"},{"key":"2_CR8","unstructured":"D.S. Hochbaum and A. Pathria. Approximating a generalization of MAX 2SAT and MIN 2SAT.To appear Discrete Applied Mathematics"},{"issue":"2","key":"2_CR9","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1287\/moor.10.2.180","volume":"10","author":"D.S. Hochbaum","year":"1985","unstructured":"D.S. Hochbaum, D.B. Shmoys. A best possible he ristic for the k-center problem. Mathematics of Operations Research 10:2, 180\u2013184, 1985.","journal-title":"Mathematics of Operations Research"},{"key":"2_CR10","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"},{"key":"2_CR11","unstructured":"D.S. Hochbaum. A framework for half integrality and 2-approximations with applications to feasible cut and minim m satisfiability.Man script UC Berkeley, (1997)."},{"key":"2_CR12","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1006\/jagm.1998.0964","volume":"29","author":"D.S. Hochbaum","year":"1998","unstructured":"D.S. Hochbaum. Approximating clique and biclique problems. Journal of Algorithms 29, 174\u2013200, (1998).","journal-title":"Journal of Algorithms"},{"issue":"3","key":"2_CR13","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1093\/forestscience\/38.3.489","volume":"38","author":"J.G. Hof","year":"1992","unstructured":"J.G. Hof and L.A. Joyce. Spacial optimization for wildlife and timber in managed forest ecosystems. Forest Science 38(3):489\u2013508, 1992.","journal-title":"Forest Science"},{"key":"2_CR14","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1287\/opre.41.2.338","volume":"41","author":"J. Orlin","year":"1993","unstructured":"J. Orlin. A faster strongly polynomial minim m cost flow algorithm. Oper-ations Research 41, 338\u2013350, 1993.","journal-title":"Oper-ations Research"}],"container-title":["Lecture Notes in Computer Science","Approximation Algorithms for Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44436-X_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T08:32:25Z","timestamp":1737102745000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44436-X_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679967","9783540444367"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-44436-x_2","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}