Leahu, Lucian; Gomes, Carla P. Quality of LP-based approximations for highly combinatorial problems. (English) Zbl 1152.68564 Wallace, Mark (ed.), Principles and practice of constraint programming – CP 2004. 10th international conference, CP 2004, Toronto, Canada, September 27–October 1, 2004. Proceedings. Berlin: Springer (ISBN 978-3-540-23241-4/pbk). Lecture Notes in Computer Science 3258, 377-392 (2004). Summary: We study the quality of LP-based approximation methods for pure combinatorial problems. We found that the quality of the LP-relaxation is a direct function of the underlying constrainedness of the combinatorial problem. More specifically, we identify a novel phase transition phenomenon in the solution integrality of the relaxation. The solution quality of approximation schemes degrades substantially near phase transition boundaries. Our findings are consistent over a range of LP-based approximation schemes. We also provide results on the extent to which LP relaxations can provide a global perspective of the search space and therefore be used as a heuristic to guide a complete solver.For the entire collection see [Zbl 1139.68008]. Cited in 1 Document MSC: 68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) 90C05 Linear programming Keywords:phase transition; approximations; search heuristics; hybrid LP/CSP PDFBibTeX XMLCite \textit{L. Leahu} and \textit{C. P. Gomes}, Lect. Notes Comput. Sci. 3258, 377--392 (2004; Zbl 1152.68564) Full Text: DOI