摘要: Linear programming has been one of the most fundamental and successful tools in optimization discrete mathematics. Its applications include exact approximation algorithms, as well structural results estimates. The key point is that linear programs are very efficiently solvable, have a powerful duality theory.
springer.com
sci-hub.se 参考文章(92)
Farid Alizadeh, Combinatorial Optimization with Semi-Definite Matrices. integer programming and combinatorial optimization. pp. 385- 405 ,(1992)
László Lovász, Alexander Schrijver, Matrix cones, projection representations, and stable set polyhedra Polyhedral Combinatorics. pp. 1- 18 ,(1990)
Ferenc Juhász, The asymptotic behaviour of Lovász' theta function for random graphs Combinatorica. ,vol. 2, pp. 153- 155 ,(1982) , 10.1007/BF02579314
Laszlo Lovasz, Integer Sequences and Semidefinite Programming pp. 4- ,(2000)
Roland Bacher, Yves Colin de Verdière, Multiplicités des valeurs propres et transformations étoile-triangle des graphes Bulletin de la Société mathématique de France. ,vol. 123, pp. 517- 533 ,(1995) , 10.24033/BSMF.2269
Romesh Saigal, Lieven Vandenberghe, Henry Wolkowicz, Handbook of semidefinite programming : theory, algorithms, and applications Kluwer Academic Publishers. ,(2000)
Nabil Kahale, A Semidefinite Bound for Mixing Rates of Markov Chains integer programming and combinatorial optimization. pp. 190- 203 ,(1996) , 10.1007/3-540-61310-2_15
Bojan Mohar, Svatopluk Poljak, Eigenvalues and the max-cut problem Czechoslovak Mathematical Journal. ,vol. 40, pp. 343- 352 ,(1990) , 10.21136/CMJ.1990.102386
Uriel Feige, Laszlo Lovasz, Two-prover one-round proof systems: Their power and their problems symposium on the theory of computing. ,(1992)
Yves Colin de Verdière, On a new graph invariant and a criterion for planarity. Graph Structure Theory. pp. 137- 147 ,(1991)