Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems

Goemans, 1995, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 1115, 10.1145/227683.227684 U. Feige, M.X. Goemans, Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT, in: Proceedings of the Third Israel Symposium on Theory of Computing and System, Tel Aviv, Israel, 1995, pp. 182–189. Lewin, 2002, Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems, vol. 2337, 67 Trevisan, 2000, Gadgets, approximation, and linear programming, SIAM J. Comput., 29, 2074, 10.1137/S0097539797328847 H. Karloff, U. Zwick, A 7/8 approximation algorithm for MAX 3SAT?, in: Proceedings of the 38th Annual Symposium on the Foundations of Computer Science, 1997, pp. 406–415. Nesterov, 1993 Burer, 2009, On the copositive representation of binary and continuous nonconvex quadratic programs, Math. Program., 120, 479, 10.1007/s10107-008-0223-z Bai, 2015, On conic QPCCs, conic QCQPs and completely positive programs, Math. Programm. Burer, 2003, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Math. Program., 95, 329, 10.1007/s10107-002-0352-8 Devolder, 2010, Solving infinite-dimensional optimization problems by polynomial approximation, 31 Helmberg, 2014, The spectral bundle method with second-order information, Optim. Methods Softw., 29, 855, 10.1080/10556788.2013.858155 Iyengar, 2011, Approximating semidefinite packing problems, SIAM J. Optim., 21, 231, 10.1137/090762671 Krishnan, 2003, Semi-infinite linear programming approaches to semidefinite programming (SDP) problems, vol. 37, 123 Krishnan, 2006, A unifying framework for several cutting plane methods for semidefinite programming, Optim. Methods Softw., 21, 57, 10.1080/10556780500065283 Lan, 2012, An optimal method for stochastic composite optimization, Math. Program., 133, 365, 10.1007/s10107-010-0434-y Li, 2014 Oskoorouchi, 2009, A second-order cone cutting surface method: complexity and application, Comput. Optim. Appl., 43, 379, 10.1007/s10589-007-9141-x Sivaramakrishnan, 2010, A parallel interior point decomposition algorithm for block angular semidefinite programs, Comput. Optim. Appl., 46, 1, 10.1007/s10589-008-9187-4 Sivaramakrishnan, 2012, Properties of a cutting plane method for semidefinite programming, Pac. J. Optim., 8, 779 Sherali, 2002, Enhancing RLT relaxations via a new class of semidefinite cuts, J. Global Optim., 22, 233, 10.1023/A:1013819515732 Oskoorouchi, 2005, An interior point cutting plane method for the convex feasibility problem with second-order cone inequalities, Math. Oper. Res., 30, 127, 10.1287/moor.1040.0116 Helmberg, 2000, A spectral bundle method for semidefinite programming, SIAM J. Optim., 10, 673, 10.1137/S1052623497328987 Helmberg, 2000 Nesterov, 1995, Cutting plane algorithms from analytic centers: efficiency estimates, Math. Program., 69, 149, 10.1007/BF01585556 Krishnan, 2006, A semidefinite programming based polyhedral cut-and-price approach for the maxcut problem, Comput. Optim. Appl., 33, 51, 10.1007/s10589-005-5958-3 Bellare, 1998, Free bits, PCPs and nonapproximability—towards tight results, SIAM J. Comput., 27, 804, 10.1137/S0097539796302531 Garey, 1976, Some simplified NP-complete graph problems, Theoret. Comput. Sci., 1, 237, 10.1016/0304-3975(76)90059-1 Poljak, 1994, The expected relative error of the polyhedral approximation of the max-cut problem, Oper. Res. Lett., 16, 191, 10.1016/0167-6377(94)90068-X Higham, 2002, Computing the nearest correlation matrix—a problem from finance, IMA J. Numer. Anal., 22, 329, 10.1093/imanum/22.3.329 Sun, 2015 Higham, 1988, Computing a nearest symmetric positive semidefinite matrix, Linear Algebra Appl., 103, 103, 10.1016/0024-3795(88)90223-6 Mitchell, 2009, Cutting plane methods and subgradient methods, 34 Qualizza, 2012, Linear programming relaxations of quadratically constrained quadratic programs, 407, 10.1007/978-1-4614-1927-3_14 Y.T. Lee, A. Sidford, S.C. Wong, A faster cutting plane method and its implications for combinatorial and convex optimization, in: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, 2015, pp. 1049–1065.