Matrix Relaxations in Combinatorial Optimization
作者： Franz Rendl
DOI: 10.1007/978-1-4614-1927-3_17
关键词:
摘要: The success of interior-point methods to solve semidefinite optimization problems (SDP) has spurred interest in SDP as a modeling tool various mathematical fields, particular combinatorial optimization. can be viewed matrix relaxation the underlying 0-1 problem. In this survey, some main techniques get relaxations are presented. These based either on matrices, leading general tractable relaxations, or completely positive copositive matrices. Copositive programs intractable, but they used exact formulations many NP-hard problems. It is purpose survey show potential relaxations.
springer.com
sci-hub.st 参考文章(71)
Ch. H. Papadimitriou, The NP-Completeness of the bandwidth minimization problem Computing. ,vol. 16, pp. 263- 270 ,(1976) , 10.1007/BF02280884
H. C. Rumsey, R. J. Mceliece, E. R. Rodemich, The Lovasz bound and some generalizations ,(1978)
Ehrhard Behrends, None, Introduction to Markov Chains Vieweg+Teubner Verlag. ,(2000) , 10.1007/978-3-322-90157-6
Naomi Shaked-Monderer, Abraham Berman, Completely Positive Matrices ,(2003)
Ehrhard Behrends, Introduction to Markov Chains: With Special Emphasis on Rapid Mixing ,(1999)
Michael Armbruster, Marzena Fügenschuh, Christoph Helmberg, Alexander Martin, A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem Integer Programming and Combinatorial Optimization. pp. 112- 124 ,(2008) , 10.1007/978-3-540-68891-4_8
Avrim Blum, David Karger, An Õ( n 3/14 )-coloring algorithm for 3-colorable graphs Information Processing Letters. ,vol. 61, pp. 49- 53 ,(1997) , 10.1016/S0020-0190(96)00190-1
Etienne de Klerk, Aspects of semidefinite programming : interior point algorithms and selected applications Kluwer Academic. ,(2002)
Immanuel M Bomze, Mirjam Dür, Etienne De Klerk, Cornelis Roos, Arie J Quist, Tamás Terlaky, On Copositive Programming and Standard Quadratic Optimization Problems Journal of Global Optimization. ,vol. 18, pp. 301- 320 ,(2000) , 10.1023/A:1026583532263
Nebojsa Gvozdenovic, Approximating the stability number and the chromatic number of a graph via semidefinite programming Universiteit van Amsterdam. ,(2008)