Sums of squares based approximation algorithms for MAX-SAT
Tài liệu tham khảo
Anjos, 2004, On semidefinite programming relaxations for the satisfiability problem, Math. Methods Oper. Res., 60, 349, 10.1007/s001860400377
Anjos, 2005, Semidefinite optimization approaches for satisfiability and maximum-satisfiability problems, J. Satisfiability Boolean Modeling Comput., 1, 1, 10.3233/SAT190001
Benson, 2000, Solving large-scale sparse semidefinite programs for combinatorial optimization, SIAM J. Optim., 10, 443, 10.1137/S1052623497328008
Blekherman, 2005, There are significantly more nonnegative polynomials than sums of squares, Israel J. Math., 153, 355, 10.1007/BF02771790
E. de Klerk, J.P. Warners, Semidefinite programming relaxations for MAX 2-SAT and 3-SAT: computational perspectives, in: P.M. Pardalos, A. Migdalas, R.E. Burkard (Eds.), Combinatorial and Global Optimization, Series on Applied Optimization, vol. 14, World Scientific Publishers, Singapore, 2002.
Feige, 1995, Approximating the value of two prover proof systems, with applications to MAX2SAT and MAXDICUT, 182
K. Fujisawa, M. Kojima, K. Nakata, M. Yamashita, SDPA (Semidefinite Programming Algorithm): user's manual, Research Reports on Information Sciences, Series B: Operations Research B 308, Department of Information Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro-ku, Tokyo, Japan, 2002.
Goemans, 1995, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach., 42, 1115, 10.1145/227683.227684
HÅstad, 2001, Some optimal inapproximability results, J. Assoc. Comput. Mach., 48, 798, 10.1145/502090.502098
Karloff, 1997, A 7/8-approximation algorithm for MAX 3SAT?
Knuth, 1969
Lewin, 2002, Improved rounding techniques for the MAX-2-SAT and MAX-DI-CUT problems, 67
Putinar, 1993, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J., 42, 10.1512/iumj.1993.42.42045
Sturm, 1999, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Software, 11–12, 625, 10.1080/10556789908805766
Zwick, 2002, Computer assisted proof of optimal approximability results, 496