Treffer: Quality of LP-based approximations for highly combinatorial problems
Title:
Quality of LP-based approximations for highly combinatorial problems
Authors:
Source:
CP 2004 : principles and practice of constraint programming (Toronto ON, 27 September - 1 October 2004)Lecture notes in computer science. :377-392
Publisher Information:
Berlin: Springer, 2004.
Publication Year:
2004
Physical Description:
print, 17 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Fonctions logiques, booléennes et de commutation, Logical, boolean and switching functions, Méthode combinatoire, Combinatorial method, Método combinatorio, Méthode heuristique, Heuristic method, Método heurístico, Optimisation combinatoire, Combinatorial optimization, Optimización combinatoria, Problème combinatoire, Combinatorial problem, Problema combinatorio, Satisfaction contrainte, Constraint satisfaction, Satisfaccion restricción
Document Type:
Konferenz
Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Dpt. of Computer Science, Cornell University, Ithaca, NY 14853, United States
ISSN:
0302-9743
Rights:
Copyright 2004 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.16177179
Database:
PASCAL Archive
Weitere Informationen
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.