{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T10:45:30Z","timestamp":1763808330242,"version":"3.41.0"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2000,2,1]],"date-time":"2000-02-01T00:00:00Z","timestamp":949363200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2000,2,1]],"date-time":"2000-02-01T00:00:00Z","timestamp":949363200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Automated Reasoning"],"published-print":{"date-parts":[[2000,2]]},"DOI":"10.1023\/a:1006362203438","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T01:36:27Z","timestamp":1040520987000},"page":"37-65","source":"Crossref","is-referenced-by-count":15,"title":["Relaxations of the Satisfiability Problem Using Semidefinite Programming"],"prefix":"10.1007","volume":"24","author":[{"given":"Etienne","family":"de Klerk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hans","family":"van Maaren","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joost P.","family":"Warners","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"255303_CR1","volume-title":"Combinatorial optimization with interior point methods and semi-definite matrices","author":"F. Alizadeh","year":"1991","unstructured":"Alizadeh, F.: Combinatorial optimization with interior point methods and semi-definite matrices, Ph.D. Thesis, University of Minnesota, Minneapolis, 1991."},{"issue":"3","key":"255303_CR2","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B. Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M. F., and Tarjan, R. E.: A linear-time algorithm for testing the truth of certain quantified Boolean formulas, Inform. Process. Lett.\n8(3) (1979), 121\u2013123.","journal-title":"Inform. Process. Lett."},{"key":"255303_CR3","series-title":"Technical Report","volume-title":"Solving large-scale sparse semidefinite programs for combinatorial optimization","author":"S. J. Benson","year":"1997","unstructured":"Benson, S. J., Ye, Y., and Zhang, X.: Solving large-scale sparse semidefinite programs for combinatorial optimization, Technical Report, Computational Optimization Lab., Department of Management Science, University of Iowa, Iowa City, 1997."},{"key":"255303_CR4","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0012-365X(73)90167-2","volume":"4","author":"V. Chv\u00e1tal","year":"1973","unstructured":"Chv\u00e1tal, V.: Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Math.\n4 (1973), 305\u2013337.","journal-title":"Discrete Math."},{"key":"255303_CR5","doi-asserted-by":"crossref","unstructured":"Cook, S. A.: The complexity of theorem proving procedures, in Proceedings of the 3rd annual ACM symposium on the Theory of Computing, 1971, pp. 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"255303_CR6","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0166-218X(87)90039-4","volume":"18","author":"W. Cook","year":"1987","unstructured":"Cook, W., Coullard, C. R., and Turan, G.: On the complexity of cutting plane proofs, Discrete Appl. Math.\n18 (1987), 25\u201338.","journal-title":"Discrete Appl. Math."},{"key":"255303_CR7","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M. Davis","year":"1962","unstructured":"Davis, M., Logemann, M., and Loveland, D.: A machine program for theorem proving, Comm. ACM\n5 (1962), 394\u2013397.","journal-title":"Comm. ACM"},{"key":"255303_CR8","volume-title":"Interior point methods for semidefinite programming","author":"E. de Klerk","year":"1997","unstructured":"de Klerk, E.: Interior point methods for semidefinite programming, Ph.D. Thesis, Delft University of Technology, Delft, The Netherlands, 1997."},{"key":"255303_CR9","unstructured":"de Klerk, E., Pasechnik, D. V., and Warners, J. P.: Approximate graph colouring algorithms based on the #-function, Technical Report, 1999. In preparation."},{"key":"255303_CR10","series-title":"Technical Report 98\u201334","volume-title":"Semidefinite programming techniques for MAX-2-SAT and MAX-3-SAT: Computational perspectives","author":"E. de Klerk","year":"1998","unstructured":"de Klerk, E. and Warners, J. P.: Semidefinite programming techniques for MAX-2-SAT and MAX-3-SAT: Computational perspectives, Technical Report 98\u201334, Department of Technical Mathematics and Informatics, Faculty of Information Technology and Systems, Delft University of Technology, Delft, The Netherlands, 1998."},{"key":"255303_CR11","unstructured":"Du, D., Gu, J., and Pardalos, P. M. (eds.): Satisfiability Problem: Theory and Applications, DIMACS Series in Discrete Math. and Comput. Sci. 35, Amer. Math. Soc., 1997."},{"key":"255303_CR12","doi-asserted-by":"crossref","unstructured":"Feige, U. and Goemans, M.: Approximating the value of two prover proof systems with applications to MAX 2SAT and MAX DICUT, in Proc. Third Israel Symposium on Theory of Computing and Systems, 1995, pp. 182\u2013189.","DOI":"10.1109\/ISTCS.1995.377033"},{"issue":"6","key":"255303_CR13","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M. X. Goemans","year":"1995","unstructured":"Goemans, M. X. and Williamson, D. P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM\n42(6) (1995), 1115\u20131145.","journal-title":"J. ACM"},{"key":"255303_CR14","unstructured":"Gu, J., Purdom, P. W., Franco, J., and Wah, B. W.: Algorithms for the satisfiability (SAT) problem: A survey, in Du et al. [11], pp. 9\u2013151."},{"key":"255303_CR15","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0304-3975(85)90144-6","volume":"39","author":"A. Haken","year":"1985","unstructured":"Haken, A.: The intractability of resolution, Theoret. Comput. Sci.\n39 (1985), 297\u2013308.","journal-title":"Theoret. Comput. Sci."},{"key":"255303_CR16","series-title":"Technical Report ZIB, Preprint SC\u201397\u201337","volume-title":"A spectral bundle method for SDP","author":"C. Helmberg","year":"1997","unstructured":"Helmberg, C. and Rendl, F.: A spectral bundle method for SDP, Technical Report ZIB, Preprint SC\u201397\u201337, Konrad-Zuse-Zentrum, Berlin, 1997."},{"issue":"1","key":"255303_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0167-6377(88)90044-2","volume":"7","author":"J. N. Hooker","year":"1988","unstructured":"Hooker, J. N.: Resolution vs. cutting plane solution of inference problems: some computational experience, Oper. Res. Lett.\n7(1) (1988), 1\u20137.","journal-title":"Oper. Res. Lett."},{"key":"255303_CR18","doi-asserted-by":"crossref","unstructured":"Horn, R. A. and Johnson, C. R.: Matrix Analysis, Cambridge University Press, 1985.","DOI":"10.1017\/CBO9780511810817"},{"key":"255303_CR19","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Pitassi, T., and Urquhart, A.: Upper and lower bounds for treelike cutting plane proofs, in Proceedings of the 9th Annual IEEE Symposium on Logic in Computer Science, 1994, pp. 220\u2013228.","DOI":"10.1109\/LICS.1994.316069"},{"key":"255303_CR20","doi-asserted-by":"crossref","unstructured":"Karloff, H. and Zwick, U.: A 7\/8-approximation algorithm for MAX3SAT? in Proceedings of the 38th Symposium on the Foundations of Computer Science, 1997, pp. 406\u2013415.","DOI":"10.1109\/SFCS.1997.646129"},{"key":"255303_CR21","volume-title":"Investigations on autark assignments","author":"O. Kullmann","year":"1998","unstructured":"Kullmann, O.: Investigations on autark assignments, Technical Report, Johann Wolfgang Goethe-Universit\u00e4t, Fachbereich Mathematik, 60054 Frankfurt, Germany, 1998. Submitted."},{"key":"255303_CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L. Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: On the Shannon capacity of a graph, IEEE Trans. Inform. Theory\n25 (1979), 1\u20137.","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"2","key":"255303_CR23","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L. Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L. and Schrijver, A.: Cones of matrices and set-functions and 0\u20131 optimization, SIAM J. Optim.\n1(2) (1991), 166\u2013190.","journal-title":"SIAM J. Optim."},{"key":"255303_CR24","series-title":"Technical Report 96\u201365","volume-title":"Elliptic approximations of propositional formulae","author":"H. Van Maaren","year":"1996","unstructured":"Van Maaren, H.: Elliptic approximations of propositional formulae, Technical Report 96\u201365, Faculty of Technical Mathematics and Informatics, Delft University of Technology, Delft, The Netherlands, 1996. To appear in Discrete Appl. Math."},{"key":"255303_CR25","doi-asserted-by":"crossref","unstructured":"Van Maaren, H.: On the use of second order derivatives for the satisfiability problem, in Du et al. [11], pp. 677\u2013687.","DOI":"10.1090\/dimacs\/035\/21"},{"key":"255303_CR26","volume-title":"Solving satisfiability problems using elliptic approximations-a note on volumes and weights","author":"H. Van Maaren","year":"1998","unstructured":"Van Maaren, H. and Warners, J. P.: Solving satisfiability problems using elliptic approximations-a note on volumes and weights, Technical Report 98\u201332, Department of Technical Mathematics and Informatics, Faculty of Information Technology and Systems, Delft University of Technology, Delft, The Netherlands, 1998."},{"key":"255303_CR27","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0166-218X(85)90050-2","volume":"10","author":"B. Monien","year":"1985","unstructured":"Monien, B. and Speckenmeyer, E.: Solving satisfiability in less than 2n steps, Discrete Appl. Math.\n10 (1985), 287\u2013295.","journal-title":"Discrete Appl. Math."},{"key":"255303_CR28","doi-asserted-by":"crossref","unstructured":"Schaefer, T. J.: The complexity of satisfiability problems, in Proceedings of the Tenth Symposium on the Theory of Computing, 1978, pp. 216\u2013226.","DOI":"10.1145\/800133.804350"},{"issue":"3","key":"255303_CR29","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"H. D. Sherali","year":"1990","unstructured":"Sherali, H. D. and Adams, W. P.: A hierarchy of relaxations between the continuous and convex hull representations for 0\u20131 programming problems, SIAM J. Discrete Math.\n3(3) (1990), 411\u2013430.","journal-title":"SIAM J. Discrete Math."},{"key":"255303_CR30","unstructured":"Strang, G.: Linear Algebra and Its Applications, 3rd edn, Harcourt Brace Jovanovich, 1988."},{"key":"255303_CR31","series-title":"Technical Report","volume-title":"Using SeDuMi 1:02, a MATLAB toolbox for optimization over symmetric cones","author":"J. F. Sturm","year":"1998","unstructured":"Sturm, J. F.: Using SeDuMi 1:02, a MATLAB toolbox for optimization over symmetric cones, Technical Report, Communications Research Laboratory, McMaster University, Hamilton, Canada, 1998."},{"key":"255303_CR32","doi-asserted-by":"crossref","unstructured":"Trevisan, L., Sorkin, G., Sudan, M., and Williamson, D.: Gadgets, approximation and linear programming, in Proceedings of the 37th Symposium on the Foundations of Computer Science, 1996, pp. 617\u2013626.","DOI":"10.1109\/SFCS.1996.548521"},{"key":"255303_CR33","unstructured":"Urquhart, A.: Open Problem Posed at SAT'98, Paderborn, Germany, 1998."},{"key":"255303_CR34","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1137\/1038003","volume":"38","author":"L. Vandenberghe","year":"1996","unstructured":"Vandenberghe, L. and Boyd, S.: Semidefinite programming, SIAM Rev.\n38 (1996), 49\u201395.","journal-title":"SIAM Rev."},{"key":"255303_CR35","doi-asserted-by":"crossref","unstructured":"Warners, J. P. and Van Maaren, H.: Recognition of tractable satisfiability problems through balanced polynomial representations, Discrete Appl. Math., 1999. To appear.","DOI":"10.1016\/S0166-218X(99)00135-3"},{"key":"255303_CR36","series-title":"Technical Report 98\u201318","volume-title":"Solving satisfiability problems using elliptic approximations-effective branching rules","author":"J. P. Warners","year":"1998","unstructured":"Warners, J. P. and Van Maaren, H.: Solving satisfiability problems using elliptic approximations-effective branching rules, Technical Report 98\u201318, Department of Technical Mathematics and Informatics, Faculty of Information Technology and Systems, Delft University of Technology, Delft, The Netherlands, 1998. Accepted for publication in Discrete Appl. Math."},{"issue":"3\u20135","key":"255303_CR37","first-page":"81","volume":"23","author":"J. P. Warners","year":"1999","unstructured":"Warners, J. P. and Van Maaren, H.: A two-phase algorithm for solving a class of hard satisfiability problems, Oper. Res. Lett.\n23(3\u20135) (1999), 81\u201388.","journal-title":"Oper. Res. Lett."}],"container-title":["Journal of Automated Reasoning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1006362203438.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1006362203438\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1006362203438.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,5]],"date-time":"2025-06-05T11:27:20Z","timestamp":1749122840000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1006362203438"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,2]]},"references-count":37,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2000,2]]}},"alternative-id":["255303"],"URL":"https:\/\/doi.org\/10.1023\/a:1006362203438","relation":{},"ISSN":["0168-7433","1573-0670"],"issn-type":[{"type":"print","value":"0168-7433"},{"type":"electronic","value":"1573-0670"}],"subject":[],"published":{"date-parts":[[2000,2]]}}}