Semidefinite programming and integer programming
作者： Monique Laurent , Franz Rendl
DOI: 10.1016/S0927-0507(05)12008-8
关键词:
摘要: Abstract This chapter surveys how semidefinite programming can be used for finding good approximative solutions to hard combinatorial optimization problems. The begins with a general presentation of several methods constructing hierarchies linear and/or relaxations 0/1 Then it moves an in-depth study two prominent problems: the maximum stable set problem and max-cut problem. Details are given about approximation stability number by Lovasz theta Goemans-Williamson algorithm max-cut, results which plays essential role, we survey some extensions these other
elsevier.com
sci-hub.se 参考文章(227)
Monique Laurent, Semidefinite Relaxations for Max-Cut. The Sharpest Cut. pp. 257- 290 ,(2004)
H. C. Rumsey, R. J. Mceliece, E. R. Rodemich, The Lovasz bound and some generalizations ,(1978)
Sanjeeb Dash, On the Matrix Cuts of Lovász and Schrijver and Their Use in Integer Programming ,(2001)
Svatopluk Poljak, Zsolt Tuza, Maximum cuts and largest bipartite subgraphs. Combinatorial Optimization. pp. 181- 244 ,(1993)
Karpinski Marek, Jansen Klaus, Lingas Andrzej, A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs Electronic Colloquium on Computational Complexity. ,vol. 7, ,(2000)
Uriel Feige, Michael Langberg, Marek Karpinski, A Note on Approximating MAX-BISECTION on Regular Graphs Electronic Colloquium on Computational Complexity. ,vol. 7, ,(2000)
J. Bochnak, M. Coste, M-F Roy, Géométrie algébrique réelle Springer-Verlag. ,(1987)
Recent advances in algorithms and combinatorics Springer New York. ,(2003) , 10.1007/B98891
High performance optimization Kluwer Academic. ,(2000) , 10.1007/978-1-4757-3216-0
Nelson Maculan, The Steiner Problem in Graphs North-holland Mathematics Studies. ,vol. 132, pp. 185- 211 ,(1987) , 10.1016/S0304-0208(08)73236-5