{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,10]],"date-time":"2024-04-10T09:08:25Z","timestamp":1712740105803},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2004,10,1]],"date-time":"2004-10-01T00:00:00Z","timestamp":1096588800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2005,1]]},"DOI":"10.1007\/s10107-003-0495-2","type":"journal-article","created":{"date-parts":[[2005,2,4]],"date-time":"2005-02-04T15:17:42Z","timestamp":1107530262000},"page":"589-608","source":"Crossref","is-referenced-by-count":9,"title":["An improved semidefinite programming relaxation for the satisfiability problem"],"prefix":"10.1007","volume":"102","author":[{"given":"Miguel F.","family":"Anjos","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2004,10,1]]},"reference":[{"key":"CR1","unstructured":"Anjos, M.F.: New Convex Relaxations for the Maximum Cut and VLSI Layout Problems. PhD thesis, University of Waterloo, 2001, Published online at http:\/\/etd.uwaterloo.ca\/etd\/manjos2001.pdf"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1023\/A:1014895808844","volume":"6","author":"Anjos","year":"3","unstructured":"Anjos, M.F., Wolkowicz, H.: Geometry of semidefinite max-cut relaxations via matrix ranks. J. Comb. Optim. 6 (3), 237?270 (2002)","journal-title":"J. Comb. Optim."},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"Anjos, M.F., Wolkowicz, H.: Semidefinite programming for discrete optimization and matrix completion problems. Discr. App. Math. 123 (1?2), 513?577 (2002)","DOI":"10.1016\/S0166-218X(01)00352-3"},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"Anjos, M.F., Wolkowicz, H.: Strengthened semidefinite relaxations via a second lifting for the max-cut problem. Discr. App. Math. 119 (1?2), 79?106 (2002)","DOI":"10.1016\/S0166-218X(01)00266-9"},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"Balas, E., Ceria, S., Cornu\u00e9jols, G.: A lift-and-project cutting plane algorithm for mixed 0?1 programs. Math. Programming 58 (3, Ser. A), 295?324 (1993)","DOI":"10.1007\/BF01581273"},{"key":"CR6","unstructured":"Bauschke, H.H. Kruk, S.G.: The method of reflection-projection for convex feasibility problems with an obtuse cone. Technical report, Oakland University, Rochester MI, U.S.A., February 2002"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1137\/S1052623497328008","volume":"10","author":"Benson","year":"2","unstructured":"Benson, S.J., Ye, Y., Zhang, X.: Solving large-scale sparse semidefinite programs for combinatorial optimization. SIAM J. Optim. 10 (2), 443?461 (electronic), (2000)","journal-title":"SIAM J. Optim."},{"key":"CR8","unstructured":"Bienstock, D., Zuckerberg, M.: Subset algebra lift operators for 0-1 integer programming. Technical Report CORC 2002-01, Columbia University, July 2002"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"Burer, S.: Semidefinite programming in the space of partial positive semidefinite matrices. Technical report, Department of Management Sciences, University of Iowa, May 2002","DOI":"10.1137\/S105262340240851X"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"1107","DOI":"10.1145\/210118.210137","volume":"42","author":"Conforti","year":"5","unstructured":"Conforti, M., Cornu\u00e9jols, G.: A class of logic problems solvable by linear programming. J. Assoc. Comput. Mach. 42 (5), 1107?1113 (1995)","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1023\/A:1021208315170","volume":"37","author":"Klerk","year":"3","unstructured":"de Klerk, E., van Maaren, H.: On semidefinite programming relaxations of (2+p)-SAT. Ann. Math. Artificial Intelligence 37 (3), 285?305 (2003)","journal-title":"Ann. Math. Artificial Intelligence"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"de Klerk, E., van Maaren, H., Warners, J.P.: Relaxations of the satisfiability problem using semidefinite programming. J. Automat. Reason. 24 (1?2), 37?65 (2000)","DOI":"10.1023\/A:1006362203438"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/347837.347842","volume":"26","author":"Ferris","year":"1","unstructured":"Ferris, M., Mesnier, M., Mor\u00e9, J.: NEOS and Condor: Solving optimization problems over the Internet. ACM Trans. Math. Softw. 26 (1), 1?18 (2000)","journal-title":"ACM Trans. Math. Softw."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1137\/S1052623400366218","volume":"11","author":"Fukuda","year":"01","unstructured":"Fukuda, M., Kojima, M., Murota, K., Nakata, K.: Exploiting sparsity in semidefinite programming via matrix completion I: General framework. SIAM J. Optim., 11 3 (01), 647?674 (electronic), (2000)","journal-title":"SIAM J. Optim.,"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"Goemans","year":"4","unstructured":"Goemans, M.X., Williamson, D.P.: New approximation algorithms for the maximum satisfiability problem. SIAM J. Disc. Math. 7 (4), 656?666 (1994)","journal-title":"SIAM J. Disc. Math."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"Goemans","year":"6","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach. 42 (6), 1115?1145 (1995)","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"647","DOI":"10.17323\/1609-4514-2002-2-4-647-679","volume":"2","author":"Grigoriev","year":"4","unstructured":"Grigoriev, D., Hirsch, E.A., Pasechnik, D.V.: Complexity of semialgebraic proofs. Moscow Math. J. 2 (4), 647?679 (2002)","journal-title":"Moscow Math. J."},{"key":"CR18","first-page":"361","volume":"6","author":"Gu","year":"3","unstructured":"Gu, J.: Global optimization for satisfiability (SAT) problem. IEEE Trans. on Know. and Data Eng. 6 (3), 361?381 (1994)","journal-title":"IEEE Trans. on Know. and Data Eng."},{"key":"CR19","unstructured":"Gu, J., Purdom, P.W., Franco, J., Wah, B.W.: Algorithms for the satisfiability (SAT) problem: a survey. In: Satisfiability problem: theory and applications (Piscataway, NJ, 1996), Amer. Math. Soc., Providence, RI, 1997, pp. 19?151"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1006\/jagm.2001.1162","volume":"40","author":"Halperin","year":"2","unstructured":"Halperin, E., Zwick, U.: Approximation algorithms for MAX 4-SAT and rounding procedures for semidefinite programs. J. Algorithms 40 (2), 184?211 (2001)","journal-title":"J. Algorithms"},{"key":"CR21","unstructured":"Helmberg, C.: A cutting plane algorithm for large scale semidefinite relaxations. Technical Report ZR-01-26, Konrad-Zuse-Zentrum Berlin, October 2001. To appear in the Padberg Festschrift ?The Sharpest Cut?, SIAM"},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"Helmberg, C., Kiwiel, K.C.: A spectral bundle method with bounds. Math. Program. 93 (2, Ser. A), 173?194 (2002)","DOI":"10.1007\/s101070100270"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1137\/S1052623497328987","volume":"10","author":"Helmberg","year":"3","unstructured":"Helmberg, C., Rendl, F.: A spectral bundle method for semidefinite programming. SIAM J. Optim. 10 (3), 673?696 (electronic), (2000)","journal-title":"SIAM J. Optim."},{"key":"CR24","doi-asserted-by":"crossref","unstructured":"Henrion, D., Lasserre, J.B.: Gloptipoly - global optimization over polynomials with matlab and sedumi. Technical report, LAAS-CNRS, Toulouse, France, 2002","DOI":"10.1145\/779359.779363"},{"key":"CR25","doi-asserted-by":"crossref","unstructured":"Karloff, H., Zwick, U.: A 7\/8-approximation algorithm for MAX 3SAT? In: Proc. of 38th FOCS, 1997, pp. 406?415","DOI":"10.1109\/SFCS.1997.646129"},{"key":"CR26","unstructured":"Ko?vara, M., Stingl, M.: PENNON - a generalized augmented lagrangian method for semidefinite programming. Technical Report 286, Institute of Applied Mathematics, University of Erlangen, 2001"},{"key":"CR27","unstructured":"Ko?vara, M., Stingl, M.: PENNON - a code for convex nonlinear and semidefinite programming. Technical Report 290, Institute of Applied Mathematics, University of Erlangen, 2002"},{"key":"CR28","unstructured":"Lasserre, J.B.: Optimality conditions and LMI relaxations for 0-1 programs. Technical report, LAAS-CNRS, Toulouse, France, 2000"},{"key":"CR29","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"Lasserre","year":"3","unstructured":"Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11 (3), 796?817 (electronic), (2000\/01)","journal-title":"SIAM J. Optim."},{"key":"CR30","doi-asserted-by":"crossref","first-page":"756","DOI":"10.1137\/S1052623400380079","volume":"12","author":"Lasserre","year":"3","unstructured":"Lasserre, J.B.: An explicit equivalent positive semidefinite program for nonlinear 0-1 programs. SIAM J. Optim. 12 (3), 756?769 (electronic), (2002)","journal-title":"SIAM J. Optim."},{"key":"CR31","doi-asserted-by":"crossref","unstructured":"Laurent, M.: Semidefinite relaxations for max-cut. In: M. Gr\u00f6tschel, (ed.), The Sharpest Cut, Festschrift in Honor of M. Padberg?s 60th Birthday. SIAM, to appear","DOI":"10.1137\/1.9780898718805.ch16"},{"key":"CR32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"Lov\u00e1sz","year":"1","unstructured":"Lov\u00e1sz, L.: On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25 (1), 1?7 (1979)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"CR33","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"Lov\u00e1sz","year":"2","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1 (2), 166?190 (1991)","journal-title":"SIAM J. Optim."},{"key":"CR34","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/s10107-002-0351-9","volume":"95","author":"Nakata","year":"2003","unstructured":"Nakata, K., Fujisawa, K., Fukuda, M., Kojima, M., Murota, K.: Exploiting sparsity in semidefinite programming via matrix completion II: Implementation and numerical results. Math. Prog. 95, 303?327 (2003)","journal-title":"Math. Prog."},{"key":"CR35","doi-asserted-by":"crossref","unstructured":"Parrilo, P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Programming 96 (2, Ser. B), 293?320 (2003)","DOI":"10.1007\/s10107-003-0387-5"},{"key":"CR36","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"Sherali","year":"3","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Disc. Math. 3 (3), 411?430 (1990)","journal-title":"SIAM J. Disc. Math."},{"key":"CR37","doi-asserted-by":"crossref","unstructured":"Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11\/12 (1?4), 625?653 (1999)","DOI":"10.1080\/10556789908805766"},{"key":"CR38","doi-asserted-by":"crossref","unstructured":"Toh, K.C., Todd, M.J., T\u00fct\u00fcnc\u00fc, R.H.: SDPT3 ? a MATLAB software package for semidefinite programming, version 1. 3. Optim. Methods Softw. 11\/12 (1?4), 545?581 (1999)","DOI":"10.1080\/10556789908805762"},{"key":"CR39","doi-asserted-by":"crossref","unstructured":"van Maaren, H.: Elliptic approximations of propositional formulae. Discrete Appl. Math. 96\/97, 223?244 (1999)","DOI":"10.1016\/S0166-218X(99)00041-4"},{"key":"CR40","doi-asserted-by":"crossref","unstructured":"Warners, J.P., van Maaren, H.: A two-phase algorithm for solving a class of hard satisfiability problems. Oper. Res. Lett. 23 (3?5), 81?88 (1998)","DOI":"10.1016\/S0167-6377(98)00052-2"},{"key":"CR41","doi-asserted-by":"crossref","unstructured":"Wolkowicz, H., Saigal, R., vandenberghe, L., editors.: Handbook of semidefinite programming. Kluwer Academic Publishers, Boston, MA, 2000","DOI":"10.1007\/978-1-4615-4381-7"},{"key":"CR42","doi-asserted-by":"crossref","unstructured":"Zwick, U.: Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems. In: Proceedings of 31st STOC, 1999, pp. 679?687","DOI":"10.1145\/301250.301431"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-003-0495-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-003-0495-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-003-0495-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,2]],"date-time":"2023-05-02T00:02:28Z","timestamp":1682985748000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-003-0495-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,10,1]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["495"],"URL":"https:\/\/doi.org\/10.1007\/s10107-003-0495-2","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,10,1]]}}}