{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T16:49:31Z","timestamp":1773766171852,"version":"3.50.1"},"reference-count":122,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[2002,11,1]],"date-time":"2002-11-01T00:00:00Z","timestamp":1036108800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3911,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2002,11]]},"DOI":"10.1016\/s0166-218x(01)00352-3","type":"journal-article","created":{"date-parts":[[2002,10,14]],"date-time":"2002-10-14T15:12:20Z","timestamp":1034608340000},"page":"513-577","source":"Crossref","is-referenced-by-count":20,"title":["Semidefinite programming for discrete optimization and matrix completion problems"],"prefix":"10.1016","volume":"123","author":[{"given":"Henry","family":"Wolkowicz","sequence":"first","affiliation":[]},{"given":"Miguel","family":"F. Anjos","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(01)00352-3_BIB1","doi-asserted-by":"crossref","unstructured":"A. Alfakih, A. Khandani, H. Wolkowicz, Solving Euclidean distance matrix completion problems via semidefinite programming, Comput. Optim. Appl. 12(1\u20133) (1999) 13\u201330 (Computational optimization\u2014a tribute to Olvi Mangasarian, Part I).","DOI":"10.1023\/A:1008655427845"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB2","series-title":"Handbook of semidefinite programming: Theory, Algorithms, and Applications","first-page":"533","article-title":"Matrix completion problems","author":"Alfakih","year":"2000"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB3","unstructured":"A. Alfakih, H. Wolkowicz, A new semidefinite programming model for large sparse Euclidean distance matrix completion problems, Technical Report CORR 2000-37, University of Waterloo, Waterloo, Canada, 2000, in progress."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB4","unstructured":"F. Alizadeh, Combinatorial optimization with interior point methods and semidefinite matrices, Ph.D. Thesis, University of Minnesota, 1991."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB5","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1137\/0805002","article-title":"Interior point methods in semidefinite programming with applications to combinatorial optimization","volume":"5","author":"Alizadeh","year":"1995","journal-title":"SIAM J. Optim."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB6","unstructured":"F. Alizadeh, J.-P. Haeberly, M.V. Nayakkankuppam, M.L. Overton, S. Schmieta, SDPpack user's guide\u2014version 0.9 Beta, Technical Report TR1997-737, Courant Institute of Mathematical Sciences, NYU, New York, NY, June 1997."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB7","unstructured":"M.F. Anjos, New convex relaxations for the maximum cut and VLSI layout problems, Ph.D. Thesis, University of Waterloo, 2001."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB8","unstructured":"M.F. Anjos, H. Wolkowicz, Geometry of semidefinite max-cut relaxations via matrix ranks, J. Combin. Optim., to appear."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB9","unstructured":"M.F. Anjos, H. Wolkowicz, A strengthened SDP relaxation via a second lifting for the Max-Cut problem, Discrete Appl. Math., to appear."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB10","doi-asserted-by":"crossref","unstructured":"K.M. Anstreicher, Eigenvalue bounds versus semidefinite relaxations for the quadratic assignment problem, Technical Report, University of Iowa, Iowa City, IA, 1999.","DOI":"10.1137\/S1052623499354904"},{"issue":"1\u20133","key":"10.1016\/S0166-218X(01)00352-3_BIB11","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/S0024-3795(99)00205-0","article-title":"Strong duality for a trust-region type relaxation of the quadratic assignment problem","volume":"301","author":"Anstreicher","year":"1999","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"10.1016\/S0166-218X(01)00352-3_BIB12","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1137\/S0895479898340299","article-title":"On Lagrangian relaxation of quadratic matrix constraints","volume":"22","author":"Anstreicher","year":"2000","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"2","key":"10.1016\/S0166-218X(01)00352-3_BIB13","doi-asserted-by":"crossref","first-page":"646","DOI":"10.1137\/S0895479893249757","article-title":"The Euclidean distance matrix completion problem","volume":"16","author":"Bakonyi","year":"1995","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"3\u20134","key":"10.1016\/S0166-218X(01)00352-3_BIB14","first-page":"547","article-title":"On the matrix completion method for multidimensional moment problems","volume":"64","author":"Bakonyi","year":"1998","journal-title":"Acta Sci. Math. (Szeged)"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB15","doi-asserted-by":"crossref","unstructured":"W.W. Barrett, C.R. Johnson, M. Lundquist, Determinantal formulae for matrix completions associated with chordal graphs, Linear Algebra Appl. 121 (1989) 265\u2013289 (Linear algebra and applications, Valencia, 1987).","DOI":"10.1016\/0024-3795(89)90706-4"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB16","unstructured":"A. Barvinok, On convex properties of the quadratic image of the sphere, Technical Report, University of Michigan, 1999."},{"issue":"2","key":"10.1016\/S0166-218X(01)00352-3_BIB17","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1137\/S1052623497328008","article-title":"Solving large-scale sparse semidefinite programs for combinatorial optimization","volume":"10","author":"Benson","year":"2000","journal-title":"SIAM J. Optim."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB18","series-title":"Perturbation Bounds for Matrix Eigenvalues","volume":"Vol. 162","author":"Bhatia","year":"1987"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB19","doi-asserted-by":"crossref","unstructured":"B. Borchers, CSDP, a C library for semidefinite programming, Optim. Methods Softw. 11\/12 (1\u20134) (1999) 613\u2013623 (Interior point methods).","DOI":"10.1080\/10556789908805765"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB20","doi-asserted-by":"crossref","unstructured":"B. Borchers, SDPLIB 1.2, a library of semidefinite programming test problems, Optim. Methods Softw. 11(1) (1999) 683\u2013690 (Interior point methods).","DOI":"10.1080\/10556789908805769"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB21","doi-asserted-by":"crossref","unstructured":"S. Burer, R.D.C. Monteiro, A projected gradient algorithm for solving the maxcut SDP relaxation, Optimization Methods and Software 15 (2001) 175\u2013200.","DOI":"10.1080\/10556780108805818"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB22","unstructured":"C.C. Choi, Y. Ye, Application of semidefinite programming to circuit partitioning, Technical Report, The University of Iowa, Iowa City, IW, 1999."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB23","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0024-3795(94)00235-5","article-title":"Maximal rank Hermitian completions of partially specified Hermitian matrices","volume":"244","author":"Cohen","year":"1996","journal-title":"Linear Algebra Appl."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB24","series-title":"Distance Geometry and Molecular Conformation","author":"Crippen","year":"1988"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB25","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0024-3795(92)90304-S","article-title":"Positive semidefinite completions of partial Hermitian matrices","volume":"175","author":"Dancis","year":"1992","journal-title":"Linear Algebra Appl."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB26","doi-asserted-by":"crossref","unstructured":"A. Edelman, T. Arias, S.T. Smith, The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl. 20(2) (1999) 303\u2013353 (electronic).","DOI":"10.1137\/S0895479895290954"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB27","doi-asserted-by":"crossref","unstructured":"S.M. Fallat, C.R. Johnson, R.L. Smith, The general totally positive matrix completion problem with few unspecified entries, Electron. J. Linear Algebra 7 (2000) 1\u201320 (electronic).","DOI":"10.13001\/1081-3810.1042"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB28","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1017\/S0017089500001221","article-title":"Some convexity theorems for matrices","volume":"10","author":"Fillmore","year":"1971","journal-title":"Glasgow Math. J."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB29","series-title":"Nonconvex Programming","author":"Forg\u00f3","year":"1988"},{"issue":"4","key":"10.1016\/S0166-218X(01)00352-3_BIB30","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1023\/A:1008282830093","article-title":"Semidefinite programming relaxation for nonconvex quadratic programs","volume":"10","author":"Fujie","year":"1997","journal-title":"J. Global Optim."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB31","unstructured":"K. Fujisawa, M. Kojima, K. Nakata, SDPA semidefinite programming algorithm, Technical Report, Dept. of Information Sciences, Tokyo Institute of Technology, Tokyo, Japan, 1995."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB32","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/BF02614319","article-title":"Exploiting sparsity in primal\u2013dual interior-point methods for semidefinite programming","volume":"79","author":"Fujisawa","year":"1997","journal-title":"Math. Programming B"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB33","unstructured":"K. Fukuda, M. Kojima, K. Murota, K. Nakata, Exploiting sparsity in semidefinite programming via matrix completion I: general framework, Technical Report B-358, Dept. of Information Sciences, Tokyo Institute of Technology, Tokyo, Japan, 1999."},{"issue":"1\u20133","key":"10.1016\/S0166-218X(01)00352-3_BIB34","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0024-3795(98)10210-0","article-title":"Maximum rank matrix completion","volume":"288","author":"Geelen","year":"1999","journal-title":"Linear Algebra Appl."},{"issue":"1\u20133","key":"10.1016\/S0166-218X(01)00352-3_BIB35","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0024-3795(98)10211-2","article-title":"Positive definite completions and determinant maximization","volume":"288","author":"Glunt","year":"1999","journal-title":"Linear Algebra Appl."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB36","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/BF02614315","article-title":"Semidefinite programming in combinatorial optimization","volume":"79","author":"Goemans","year":"1997","journal-title":"Math. Programming"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB37","doi-asserted-by":"crossref","unstructured":"M.X. Goemans, Semidefinite programming and combinatorial optimization, Documenta Math. (Extra Volume ICM) 1998 (1998) 657\u2013666 (Invited talk at the International Congress of Mathematicians, Berlin, 1998).","DOI":"10.4171\/dms\/1-3\/63"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB38","series-title":"Handbook of Semidefinite Programming: Theory, Algorithms, and Applications","article-title":"Combinatorial optimization","author":"Goemans","year":"2000"},{"issue":"6","key":"10.1016\/S0166-218X(01)00352-3_BIB39","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","article-title":"Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming","volume":"42","author":"Goemans","year":"1995","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB40","series-title":"Partially Specified Matrices and Operators: Classification, Completion, Applications","author":"Gohberg","year":"1995"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB41","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0024-3795(84)90207-6","article-title":"Positive definite completions of partial Hermitian matrices","volume":"58","author":"Grone","year":"1984","journal-title":"Linear Algebra Appl."},{"issue":"3","key":"10.1016\/S0166-218X(01)00352-3_BIB42","doi-asserted-by":"crossref","first-page":"727","DOI":"10.1287\/moor.17.3.727","article-title":"A new lower bound via projection for the quadratic assignment problem","volume":"17","author":"Hadley","year":"1992","journal-title":"Math. Oper. Res."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB43","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1109\/TIT.1979.1056027","article-title":"On some problems of Lov\u00e1sz concerning the Shannon capacity of graphs","volume":"25","author":"Haemers","year":"1979","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"1\u20133","key":"10.1016\/S0166-218X(01)00352-3_BIB44","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/S0024-3795(99)00065-8","article-title":"Methods for constructing distance matrices and the inverse eigenvalue problem","volume":"295","author":"Hayden","year":"1999","journal-title":"Linear Algebra Appl."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB45","unstructured":"C. Helmberg, An interior-point method for semidefinite programming and max-cut bounds, Ph.D. Thesis, Graz University of Technology, Austria, 1994."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB46","series-title":"Handbook of Semidefinite Programming: Theory, Algorithms, and Applications","article-title":"Bundle methods to minimize the maximum eigenvalue function","author":"Helmberg","year":"2000"},{"issue":"3","key":"10.1016\/S0166-218X(01)00352-3_BIB47","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1137\/S1052623497328987","article-title":"A spectral bundle method for semidefinite programming","volume":"10","author":"Helmberg","year":"2000","journal-title":"SIAM J. Optim."},{"issue":"2","key":"10.1016\/S0166-218X(01)00352-3_BIB48","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1137\/0806020","article-title":"An interior-point method for semidefinite programming","volume":"6","author":"Helmberg","year":"1996","journal-title":"SIAM J. Optim."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB49","unstructured":"B. Hendrickson, The molecule problem: Determining conformation from pairwise distances, Ph.D. Thesis, Cornell University, Ithaca, New York, 1991."},{"issue":"4","key":"10.1016\/S0166-218X(01)00352-3_BIB50","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1137\/0805040","article-title":"The molecule problem: exploiting structure in global optimization","volume":"5","author":"Hendrickson","year":"1995","journal-title":"SIAM J. Optim."},{"issue":"1\u20133","key":"10.1016\/S0166-218X(01)00352-3_BIB51","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/S0024-3795(98)10054-X","article-title":"Completions of inverse M-matrix patterns","volume":"282","author":"Hogben","year":"1998","journal-title":"Linear Algebra Appl."},{"issue":"1\u20133","key":"10.1016\/S0166-218X(01)00352-3_BIB52","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/S0024-3795(98)10120-9","article-title":"Completions of M-matrix patterns","volume":"285","author":"Hogben","year":"1998","journal-title":"Linear Algebra Appl."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB53","unstructured":"S. Homer, M. Peinado, In the performance of polynomial-time clique algorithms on very large graphs, Technical Report, Boston University, Boston, MA, 1994."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB54","unstructured":"R.A. Horn, C.R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1990 (Corrected reprint of the 1985 original)."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB55","doi-asserted-by":"crossref","unstructured":"C.R. Johnson, Matrix completion problems: a survey, Matrix Theory and Applications, Phoenix, AZ, 1989, Amer. Math. Soc., Providence, RI, 1990, pp. 171\u2013198.","DOI":"10.1090\/psapm\/040\/1059486"},{"issue":"2","key":"10.1016\/S0166-218X(01)00352-3_BIB56","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1023\/A:1018363021404","article-title":"An interior-point method for approximate positive semidefinite completions","volume":"9","author":"Johnson","year":"1998","journal-title":"Comput. Optim. Appl."},{"issue":"electronic","key":"10.1016\/S0166-218X(01)00352-3_BIB57","first-page":"59","article-title":"The combinatorially symmetric P-matrix completion problem","volume":"1","author":"Johnson","year":"1996","journal-title":"Electron. J. Linear Algebra"},{"issue":"1\u20134","key":"10.1016\/S0166-218X(01)00352-3_BIB58","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1080\/03081088408817622","article-title":"Inertia possibilities for completions of partial Hermitian matrices","volume":"16","author":"Johnson","year":"1984","journal-title":"Linear Multilinear Algebra"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB59","doi-asserted-by":"crossref","unstructured":"C.R. Johnson, L. Rodman, Chordal inheritance principles and positive definite completions of partial matrices over function rings, Contributions to Operator Theory and its Applications, Mesa, AZ, 1987, Birkh\u00e4user, Basel, 1988, pp. 107\u2013127.","DOI":"10.1007\/978-3-0348-9284-1_5"},{"issue":"1\u20133","key":"10.1016\/S0166-218X(01)00352-3_BIB60","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/S0024-3795(98)10230-6","article-title":"The symmetric inverse M-matrix completion problem","volume":"290","author":"Johnson","year":"1999","journal-title":"Linear Algebra Appl."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB61","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/0024-3795(95)00096-A","article-title":"Connections between the real positive semidefinite and distance matrix completion problems (special issue honoring Miroslav Fiedler and Vlastimil Pt\u00e1k)","volume":"223\/224","author":"Johnson","year":"1995","journal-title":"Linear Algebra Appl."},{"issue":"4","key":"10.1016\/S0166-218X(01)00352-3_BIB62","doi-asserted-by":"crossref","first-page":"861","DOI":"10.1137\/S0895479896311517","article-title":"Approximate semidefinite matrices in a subspace","volume":"19","author":"Johnson","year":"1999","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB63","doi-asserted-by":"crossref","unstructured":"S.E. Karisch, F. Rendl, H. Wolkowicz, Trust regions and relaxations for the quadratic assignment problem, Quadratic Assignment and Related Problems, New Brunswick, NJ, 1993, Amer. Math. Soc., Providence, RI, 1994, pp. 199\u2013219.","DOI":"10.1090\/dimacs\/016\/10"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB64","doi-asserted-by":"crossref","unstructured":"D.E. Knuth, The sandwich theorem, Electron. J. Combin. 1 (1994) 48pp.","DOI":"10.37236\/1193"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB65","unstructured":"M. Kojima, S. Kojima, S. Hara, Linear algebra for semidefinite programming, Technical Report 1004, Dept. of Information Sciences, Tokyo Institute of Technology, Tokyo, Japan, 1997 (Linear matrix inequalities and positive semidefinite programming, Kyoto, 1996 (Japanese))."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB66","unstructured":"M. Kojima, L. Tun\u00e7el, Discretization and localization in successive convex relaxation methods for nonconvex quadratic optimization problems, Technical Report CORR98-34, Dept. of Combinatorics and Optimization, University of Waterloo, 1998."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB67","doi-asserted-by":"crossref","unstructured":"M. Kojima, L. Tun\u00e7el, Cones of matrices and successive convex relaxations of nonconvex sets, SIAM J. Optim. 10 (2000) 750\u2013778.","DOI":"10.1137\/S1052623498336450"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB68","unstructured":"M. Kojima, L. Tun\u00e7el, On the finite convergence of successive convex relaxation methods, Technical Report CORR99-36, Dept. of Combinatorics and Optimization, University of Waterloo, 1999."},{"issue":"5","key":"10.1016\/S0166-218X(01)00352-3_BIB69","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1080\/02331938808843386","article-title":"A tight bound for the Boolean quadratic optimization problem and its use in a branch and bound algorithm","volume":"19","author":"K\u00f6rner","year":"1988","journal-title":"Optimization"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB70","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1080\/02331939208843863","article-title":"Remarks on a difficult test problem for quadratic Boolean programming","volume":"26","author":"K\u00f6rner","year":"1992","journal-title":"Optimization"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB71","unstructured":"S. Kruk, Semidefinite programming applied to nonlinear programming, Master's Thesis, University of Waterloo, 1996."},{"issue":"1","key":"10.1016\/S0166-218X(01)00352-3_BIB72","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1080\/10556780108805808","article-title":"The Gauss-Newton direction in linear and semidefinite programming","volume":"15","author":"Kruk","year":"2001","journal-title":"Optim. Methods Softw."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB73","doi-asserted-by":"crossref","unstructured":"S. Kruk, H. Wolkowicz, sq2p, sequential quadratic constrained quadratic programming, Advances in Nonlinear Programming, Beijing, 1996, Kluwer Acad. Publ., Dordrecht, 1998, pp. 177\u2013204.","DOI":"10.1007\/978-1-4613-3335-7_8"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB74","doi-asserted-by":"crossref","unstructured":"J.B. Lasserre, Optimality conditions and lmi relaxations for 0\u20131 programs, Laas Research Report, LAAS-CNRS, Toulouse, France, 2000.","DOI":"10.1109\/CDC.2001.914738"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB75","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF02614320","article-title":"Cuts, matrix completions and graph rigidity","volume":"79","author":"Laurent","year":"1997","journal-title":"Math. Programming"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB76","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/S0024-3795(97)83714-7","article-title":"A connection between positive semidefinite and Euclidean distance matrix completion problems","volume":"273","author":"Laurent","year":"1998","journal-title":"Linear Algebra Appl."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB77","doi-asserted-by":"crossref","unstructured":"M. Laurent, A tour d'horizon on positive semidefinite and Euclidean distance matrix completion problems, Topics in Semidefinite and Interior-Point Methods, The Fields Institute for Research in Mathematical Sciences, Communications Series, Vol. 18, American Mathematical Society, Providence, RI, 1998, pp. 51\u201376.","DOI":"10.1090\/fic\/018\/05"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB78","doi-asserted-by":"crossref","unstructured":"M. Laurent, Polynomial instances of the positive semidefinite and Euclidean distance matrix completion problems, SIAM J. Matrix Anal. Appl. 22 (2000) 874\u2013894.","DOI":"10.1137\/S0895479899352689"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB79","unstructured":"C. Lemar\u00e9chal, F. Oustry, Semidefinite relaxations and Lagrangian duality with application to combinatorial optimization, Technical Report, Institut National de Recherche en Informatique et en Automatique, INRIA, St Martin, France, 1999."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB80","unstructured":"M. Littman, D.F. Swayne, N. Dean, A. Buja, Visualizing the embedding of objects in Euclidean space, Technical Report, Bellcore, Morristown, NJ 07962-1910, 1999."},{"issue":"2","key":"10.1016\/S0166-218X(01)00352-3_BIB81","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","article-title":"Cones of matrices and set-functions and 0\u20131 optimization","volume":"1","author":"Lov\u00e1sz","year":"1991","journal-title":"SIAM J. Optim."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB82","series-title":"Optimization by Vector Space Methods","author":"Luenberger","year":"1969"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB83","unstructured":"Z-Q. Luo, S. Zhang, On the extension of Frank-Wolfe theorem, Technical Report, Erasmus University Rotterdam, The Netherlands, 1997."},{"issue":"4","key":"10.1016\/S0166-218X(01)00352-3_BIB84","first-page":"905","article-title":"Matrix completions, norms and Hadamard products","volume":"117","author":"Mathias","year":"1993","journal-title":"Proc. Amer. Math. Soc."},{"issue":"4","key":"10.1016\/S0166-218X(01)00352-3_BIB85","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1287\/moor.18.4.964","article-title":"On adaptive-step primal\u2013dual interior-point algorithms for linear programming","volume":"18","author":"Mizuno","year":"1993","journal-title":"Math. Oper. Res."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB86","series-title":"Eigenvalues in combinatorial optimization, Combinatorial Graph-Theoretical Problems in Linear Algebra, IMA Vol. 50","author":"Mohar","year":"1993"},{"issue":"3","key":"10.1016\/S0166-218X(01)00352-3_BIB87","doi-asserted-by":"crossref","first-page":"663","DOI":"10.1137\/S1052623495293056","article-title":"Primal\u2013dual path-following algorithms for semidefinite programming","volume":"7","author":"Monteiro","year":"1997","journal-title":"SIAM J. Optim."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB88","unstructured":"R.D.C. Monteiro, P.R. Zanj\u00e1como, Implementation of primal\u2013dual methods for semidefinite programming based on Monteiro and Tsuchiya Newton directions and their variants, Technical Report, Georgia Tech, Atlanta, GA, 1997."},{"issue":"3","key":"10.1016\/S0166-218X(01)00352-3_BIB89","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1023\/A:1008380219900","article-title":"Distance geometry optimization for protein structures","volume":"15","author":"Mor\u00e9","year":"1999","journal-title":"J. Global Optim."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB90","unstructured":"Y.E. Nesterov, Quality of semidefinite relaxation for nonconvex quadratic optimization, Technical Report, CORE, Universite Catholique de Louvain, Belgium, 1997."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB91","unstructured":"Y.E. Nesterov, A.S. Nemirovski, Optimization over Positive Semidefinite Matrices: Mathematical Background and User's Manual, USSR Acad. Sci. Centr. Econ. & Math. Inst., 32 Krasikova St., Moscow 117418 USSR, 1990."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB92","series-title":"Interior Point Polynomial Algorithms in Convex Programming","author":"Nesterov","year":"1994"},{"issue":"1","key":"10.1016\/S0166-218X(01)00352-3_BIB93","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.22.1.1","article-title":"Self-scaled barriers and interior-point methods for convex programming","volume":"22","author":"Nesterov","year":"1997","journal-title":"Math. Oper. Res."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB94","series-title":"Handbook of Semidefinite Programming: Theory, Algorithms, and Applications","first-page":"361","article-title":"Semidefinite programming relaxations of nonconvex quadratic optimization","author":"Nesterov","year":"2000"},{"issue":"1","key":"10.1016\/S0166-218X(01)00352-3_BIB95","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1090\/S0002-9939-1985-0781052-8","article-title":"Matrix completion theorems","volume":"94","author":"Newman","year":"1985","journal-title":"Proc. Amer. Math. Soc."},{"issue":"2, Ser. B","key":"10.1016\/S0166-218X(01)00352-3_BIB96","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/BF01585173","article-title":"Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices","volume":"62","author":"Overton","year":"1993","journal-title":"Math. Programming"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB97","unstructured":"P. Pardalos, F. Rendl, H. Wolkowicz, The quadratic assignment problem: a survey and recent developments. in: P. Pardalos, H. Wolkowicz, (Eds.), Quadratic Assignment and Related Problems, New Brunswick, NJ, 1993. Amer. Math. Soc., Providence, RI, 1994, pp. 1\u201342."},{"issue":"1","key":"10.1016\/S0166-218X(01)00352-3_BIB98","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/BF00120662","article-title":"Quadratic programming with one negative eigenvalue is NP-hard","volume":"1","author":"Pardalos","year":"1991","journal-title":"J. Global Optim."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB99","doi-asserted-by":"crossref","unstructured":"B.N. Parlett, The Symmetric Eigenvalue Problem, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998 (Corrected reprint of the 1980 original).","DOI":"10.1137\/1.9781611971163"},{"issue":"1","key":"10.1016\/S0166-218X(01)00352-3_BIB100","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/BF01100205","article-title":"A recipe for semidefinite relaxation for (0,1)-quadratic programming","volume":"7","author":"Poljak","year":"1995","journal-title":"J. Global Optim."},{"issue":"3","key":"10.1016\/S0166-218X(01)00352-3_BIB101","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1287\/moor.20.3.550","article-title":"Convex relaxations of (0,1)-quadratic programming","volume":"20","author":"Poljak","year":"1995","journal-title":"Math. Oper. Res."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB102","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1080\/10556789808805692","article-title":"Copositive relaxation for general quadratic programming (special issue Celebrating the 60th Birthday of Professor Naum Shor)","volume":"9","author":"Quist","year":"1998","journal-title":"Optim. Methods Softw."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB103","unstructured":"M.V. Ramana, An algorithmic analysis of multiquadratic and semidefinite programming problems, Ph.D. Thesis, Johns Hopkins University, Baltimore, MD, 1993."},{"issue":"3","key":"10.1016\/S0166-218X(01)00352-3_BIB104","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1137\/S1052623495288350","article-title":"Strong duality for semidefinite programming","volume":"7","author":"Ramana","year":"1997","journal-title":"SIAM J. Optim."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB105","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/S0168-9274(98)00097-X","article-title":"Semidefinite programming and combinatorial optimization","volume":"29","author":"Rendl","year":"1999","journal-title":"Appl. Numer. Math."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB106","doi-asserted-by":"crossref","unstructured":"F. Rendl, H. Wolkowicz, A projection technique for partitioning the nodes of a graph, Ann. Oper. Res. 58 (1995) 155\u2013179 (Applied mathematical programming and modeling, II (APMOD 93), Budapest, 1993).","DOI":"10.1007\/BF02032130"},{"issue":"2, Ser. B","key":"10.1016\/S0166-218X(01)00352-3_BIB107","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/BF02614438","article-title":"A semidefinite framework for trust region subproblems with applications to large scale minimization","volume":"77","author":"Rendl","year":"1997","journal-title":"Math. Programming"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB108","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1109\/TIT.1979.1056072","article-title":"A comparison of the Delsarte and Lov\u00e1sz bounds","volume":"IT-25","author":"Schrijver","year":"1979","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"1","key":"10.1016\/S0166-218X(01)00352-3_BIB109","first-page":"128","article-title":"Quadratic optimization problems","volume":"222","author":"Shor","year":"1987","journal-title":"Izv. Akad. Nauk SSSR Tekhn. Kibernet."},{"issue":"2","key":"10.1016\/S0166-218X(01)00352-3_BIB110","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1137\/0805016","article-title":"Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations","volume":"5","author":"Stern","year":"1995","journal-title":"SIAM J. Optim."},{"issue":"1\u20134","key":"10.1016\/S0166-218X(01)00352-3_BIB111","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1080\/10556789908805766","article-title":"Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones","volume":"11\/12","author":"Sturm","year":"1999","journal-title":"Optim. Methods Softw."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB112","first-page":"1","article-title":"A study of search directions in primal\u2013dual interior-point methods for semidefinite programming","volume":"11&12","author":"Todd","year":"1999","journal-title":"Optim. Methods Softw."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB113","unstructured":"M.J. Todd, K.C. Toh, R.H. Tutuncu, A MATLAB software package for semidefinite programming, Technical Report, School of OR and IE, Cornell University, Ithaca, NY, 1996."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB114","first-page":"148","article-title":"Applications of multidimensional scaling to molecular conformation","volume":"29","author":"Trosset","year":"1998","journal-title":"Comput. Sci. Statist."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB115","unstructured":"L. Tun\u00e7el, S. Xu, Complexity analyses of discretized successive convex relaxation methods, Technical Report CORR 99-37, Department of Combinatorics and Optimization, Waterloo, Ont., 1999."},{"issue":"2","key":"10.1016\/S0166-218X(01)00352-3_BIB116","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1137\/S0895479896303430","article-title":"Determinant maximization with linear matrix inequality constraints","volume":"19","author":"Vandenberghe","year":"1998","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB117","unstructured":"C.P. Wells, An improved method for sampling of molecular conformation space, Ph.D. Thesis, University of Kentucky, 1995."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB118","doi-asserted-by":"crossref","unstructured":"H. Wolkowicz, R. Saigal, L. Vandenberghe (Eds.), Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, Kluwer Academic Publishers, Boston, MA, 2000, xxvi+654 pages.","DOI":"10.1007\/978-1-4615-4381-7_1"},{"issue":"1","key":"10.1016\/S0166-218X(01)00352-3_BIB119","first-page":"81","article-title":"The S-procedure and duality theorems for nonconvex problems of quadratic programming","volume":"1973","author":"Yakubovich","year":"1973","journal-title":"Vestnik Leningrad. Univ."},{"key":"10.1016\/S0166-218X(01)00352-3_BIB120","doi-asserted-by":"crossref","unstructured":"Y. Ye, A new complexity result on minimization of a quadratic function with a sphere constraint, Recent Advances in Global Optimization, Princeton University Press, Princeton, 1992, pp. 19\u201331.","DOI":"10.1515\/9781400862528.19"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB121","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/s10107980012a","article-title":"Approximating quadratic programming with bound and quadratic constraints","volume":"84","author":"Ye","year":"1999","journal-title":"Math. Programming"},{"key":"10.1016\/S0166-218X(01)00352-3_BIB122","unstructured":"Q. Zhao, S.E. Karisch, F. Rendl, H. Wolkowicz, Semidefinite programming relaxations for the quadratic assignment problem, J. Combin. Optim. 2 (1) (1998) 71\u2013109 (Semidefinite programming and interior-point approaches for combinatorial optimization problems, Toronto, ON, 1996)."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X01003523?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X01003523?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,4,8]],"date-time":"2023-04-08T12:24:25Z","timestamp":1680956665000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X01003523"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,11]]},"references-count":122,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2002,11]]}},"alternative-id":["S0166218X01003523"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(01)00352-3","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2002,11]]}}}