{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T05:34:17Z","timestamp":1740548057171,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540232414"},{"type":"electronic","value":"9783540302018"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30201-8_29","type":"book-chapter","created":{"date-parts":[[2010,9,22]],"date-time":"2010-09-22T21:14:37Z","timestamp":1285190077000},"page":"377-392","source":"Crossref","is-referenced-by-count":2,"title":["Quality of LP-Based Approximations for Highly Combinatorial Problems"],"prefix":"10.1007","author":[{"given":"Lucian","family":"Leahu","sequence":"first","affiliation":[]},{"given":"Carla P.","family":"Gomes","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"29_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0167-6377(88)90044-2","volume":"7","author":"J. Hooker","year":"1988","unstructured":"Hooker, J.: Resolution vs. cutting plane solution of inference problems: Some computational experience. Operations Research Letter\u00a07, 1\u20137 (1988)","journal-title":"Operations Research Letter"},{"key":"29_CR2","first-page":"1","volume":"74","author":"J. Hooker","year":"1996","unstructured":"Hooker, J.: Resolution and the integrality of satisfiability problems. Mathematical Programming\u00a074, 1\u201310 (1996)","journal-title":"Mathematical Programming"},{"key":"29_CR3","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01581082","volume":"57","author":"A. Kamath","year":"1992","unstructured":"Kamath, A., Karmarkar, N.K., Ramakrishnan, K.G., Resende, M.G.C.: A continuous approach to inductive inference. Mathematical Programming\u00a057, 215\u2013238 (1992)","journal-title":"Mathematical Programming"},{"unstructured":"Warners, J.: Nonlinear approaches to satisfiability problems. PhD thesis, Technische Universiteit Eindhoven (1999)","key":"29_CR4"},{"key":"29_CR5","first-page":"221","volume-title":"Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI 1997)","author":"C. Gomes","year":"1997","unstructured":"Gomes, C., Selman, B.: Problem Structure in the Presence of Perturbations. In: Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI 1997), New Providence, RI, pp. 221\u2013227. AAAI Press, Menlo Park (1997)"},{"key":"29_CR6","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0898-1221(94)00219-B","volume":"29","author":"J. Slaney","year":"1995","unstructured":"Slaney, J., Fujita, M., Stickel, M.: Automated reasoning and exhaustive search: Quasigroup existence problems. Computers and Math. with Applications\u00a029, 115\u2013132 (1995)","journal-title":"Computers and Math. with Applications"},{"doi-asserted-by":"crossref","unstructured":"Colbourn, C.: The complexity of completing partial latin squares. Discrete Applied Mathematics, 25\u201330 (1984)","key":"29_CR7","DOI":"10.1016\/0166-218X(84)90075-1"},{"unstructured":"Laywine, C., Mullen, G.: Discrete Mathematics using Latin Squares. Wiley- Interscience Series in Discrete mathematics and Optimization (1998)","key":"29_CR8"},{"key":"29_CR9","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1007\/PL00009274","volume":"24","author":"S.R. Kumar","year":"1999","unstructured":"Kumar, S.R., Russell, A., Sundaram, R.: Approximating latin square extensions. Algorithmica\u00a024, 128\u2013138 (1999)","journal-title":"Algorithmica"},{"key":"29_CR10","volume-title":"Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI 2000)","author":"D. Achlioptas","year":"2000","unstructured":"Achlioptas, D., Gomes, C., Kautz, H., Selman, B.: Generating Satisfiable Instances. In: Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI 2000), New Providence, RI, AAAI Press, Menlo Park (2000)"},{"unstructured":"Gomes, C., Regis, R., Shmoys, D.: An Improved Approximation Algorithm for the Partial Latin Square Extension Problem. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), Baltimore, MD, USA, pp. 832\u2013833 (2003)","key":"29_CR11"},{"doi-asserted-by":"crossref","unstructured":"Gomes, C., Shmoys, D.: Approximations and Randomization to Boost CSP Techniques. To appear in Annals of Operations Research (2004)","key":"29_CR12","DOI":"10.1023\/B:ANOR.0000032572.32788.da"},{"key":"29_CR13","volume-title":"Contributions to the Theory of Games","author":"J. Neumann von","year":"1953","unstructured":"von Neumann, J.: A certain zero-sum two-person game equivalent to the optimal assignment problem. In: Contributions to the Theory of Games, vol.\u00a02, Princeton University Press, Princeton (1953)"},{"unstructured":"Motwani, R., Naor, J., Raghavan, P.: Randomized approximation algorithms in combinatorial optimization. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-Hard Problems, PWS Publishing Company (1997)","key":"29_CR14"},{"doi-asserted-by":"crossref","unstructured":"Goemans, M.X., Willianson, D.P.: 0.878-approximation algorithms for max-cut and max-sat. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Theory of Computing, pp. 422\u2013431 (1994)","key":"29_CR15","DOI":"10.1145\/195058.195216"},{"doi-asserted-by":"crossref","unstructured":"Chudak, F., Shmoys, D.: Improved approximation algorithms for the uncapacitated facility location problem. In: Submitted for publication, Preliminary version of this paper (with the same title) appeared in proceedings of the Sixth Conference on Integer Programming and Combinatorial Optimization (1999)","key":"29_CR16","DOI":"10.1007\/3-540-69346-7_14"},{"unstructured":"Gomes, C., Williams, R.: Approximation algorithms. In: Introduction to Optimization, DecisionSupport and Search Methodologies (2004) (to appear)","key":"29_CR17"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming \u2013 CP 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30201-8_29.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T00:22:52Z","timestamp":1740529372000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30201-8_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540232414","9783540302018"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30201-8_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}