{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T12:10:35Z","timestamp":1764936635818},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,10,26]],"date-time":"2012-10-26T00:00:00Z","timestamp":1351209600000},"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":[[2012,12]]},"DOI":"10.1007\/s10107-012-0604-1","type":"journal-article","created":{"date-parts":[[2012,10,25]],"date-time":"2012-10-25T09:01:38Z","timestamp":1351155698000},"page":"279-300","source":"Crossref","is-referenced-by-count":21,"title":["Solving $$k$$ -cluster problems to optimality with semidefinite programming"],"prefix":"10.1007","volume":"136","author":[{"given":"J\u00e9r\u00f4me","family":"Malick","sequence":"first","affiliation":[]},{"given":"Fr\u00e9d\u00e9ric","family":"Roupin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,10,26]]},"reference":[{"issue":"2","key":"604_CR1","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1006\/jagm.1999.1062","volume":"34","author":"Y Asahiro","year":"2000","unstructured":"Asahiro, Y., Iwama, K., Tamaki, H., Tokuyama, T.: Greedily finding a dense subgraph. J. Algorithms 34(2), 203\u2013221 (2000)","journal-title":"J. Algorithms"},{"issue":"3","key":"604_CR2","first-page":"171","volume":"43","author":"A Billionnet","year":"2005","unstructured":"Billionnet, A.: Different formulations for solving the heaviest k-subgraph problem. Inf. Syst. Oper. Res. 43(3), 171\u2013186 (2005)","journal-title":"Inf. Syst. Oper. Res."},{"issue":"1","key":"604_CR3","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/s10107-005-0637-9","volume":"109","author":"A Billionnet","year":"2006","unstructured":"Billionnet, A., Elloumi, S.: Using a mixed integer quadratic programming solver for the unconstrained quadratic 0\u20131 problem. Math. Program. 109(1), 55\u201368 (2006)","journal-title":"Math. Program."},{"issue":"6","key":"604_CR4","doi-asserted-by":"crossref","first-page":"1185","DOI":"10.1016\/j.dam.2007.12.007","volume":"157","author":"A Billionnet","year":"2009","unstructured":"Billionnet, A., Elloumi, S., Plateau, M.-C.: Improving the performance of standard solvers for quadratic 0\u20131 programs by a tight convex reformulation: the QCR method. Discret. Appl. Math. 157(6), 1185\u20131197 (2009)","journal-title":"Discret. Appl. Math."},{"key":"604_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-05078-1","volume-title":"Numerical Optimization","author":"JF Bonnans","year":"2003","unstructured":"Bonnans, J.F., Gilbert, JCh.: Numerical Optimization. Springer, Berlin (2003)"},{"issue":"1","key":"604_CR6","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1080\/10556789908805765","volume":"11","author":"B Borchers","year":"1999","unstructured":"Borchers, B.: CSDP, a C library for semidefinite programming. Optim. Methods Softw. 11(1), 613\u2013623 (1999)","journal-title":"Optim. Methods Softw."},{"key":"604_CR7","unstructured":"Borsdorf, R., Higham, N.: A preconditionned newton algorithm for the nearest correlation matrix. Submitted (2008)"},{"key":"604_CR8","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/s10107-002-0352-8","volume":"95","author":"S Burer","year":"2003","unstructured":"Burer, S., Monteiro, R.D.C.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. (Series B) 95, 329\u2013357 (2003)","journal-title":"Math. Program. (Series B)"},{"issue":"1","key":"604_CR9","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/0166-218X(84)90088-X","volume":"9","author":"DG Corneil","year":"1984","unstructured":"Corneil, D.G., Perl, Y.: Clustering and domination in perfect graphs. Discret. Appl. Math. 9(1), 7\u201339 (1984)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"604_CR10","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/0377-2217(90)90297-O","volume":"46","author":"E Erkut","year":"1990","unstructured":"Erkut, E.: The discrete p-dispersion problem. Eur. J. Oper. Res. 46(1), 48\u201360 (1990)","journal-title":"Eur. J. Oper. Res."},{"key":"604_CR11","doi-asserted-by":"crossref","unstructured":"Faye, A., Roupin, F.: A cutting planes algorithm based upon a semidefinite relaxation for the quadratic assignment problem. In: ESA 2008, LNCS 3669, pp. 850\u2013861 (2005)","DOI":"10.1007\/11561071_75"},{"issue":"1","key":"604_CR12","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/s10288-006-0011-7","volume":"5","author":"A Faye","year":"2007","unstructured":"Faye, A., Roupin, F.: Partial lagrangian for general quadratic programming. 4\u2019OR Q. J. Oper. Res. 5(1), 75\u201388 (2007)","journal-title":"4\u2019OR Q. J. Oper. Res."},{"issue":"2","key":"604_CR13","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1006\/jagm.2001.1183","volume":"41","author":"U Feige","year":"2001","unstructured":"Feige, U., Langberg, M.: Approximation algorithms for maximization problems arising in graph partitioning. J. Algorithms 41(2), 174\u2013211 (2001)","journal-title":"J. Algorithms"},{"issue":"3","key":"604_CR14","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U Feige","year":"2001","unstructured":"Feige, U., Kortsarz, G., Peleg, D.: The dense k-subgraph problem. Algorithmica 29(3), 410\u2013421 (2001)","journal-title":"Algorithmica"},{"key":"604_CR15","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/BF01589113","volume":"45","author":"JCh Gilbert","year":"1989","unstructured":"Gilbert, JCh., Lemar\u00e9chal, C.: Some numerical experiments with variable-storage quasi-Newton algorithms. Math. Program. 45, 407\u2013435 (1989)","journal-title":"Math. Program."},{"key":"604_CR16","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"6","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 6, 1115\u20131145 (1995)","journal-title":"J. ACM"},{"issue":"3","key":"604_CR17","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1007\/s101070100288","volume":"92","author":"Q Han","year":"2002","unstructured":"Han, Q., Ye, Y., Zhang, J.: An improved rounded method and semidefinite programming relaxation for graph partition. Math. Program. 92(3), 509\u2013535 (2002)","journal-title":"Math. Program."},{"key":"604_CR18","unstructured":"Helmberg, C.: A C++ implementation of the Spectral Bundle Method. http:\/\/www-user.tu-chemnitz.de\/ helmberg\/SBmethod\/, Version 1.1.3 (2004)"},{"issue":"3","key":"604_CR19","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1137\/S1052623497328987","volume":"10","author":"C Helmberg","year":"2000","unstructured":"Helmberg, C., Rendl, F.: A spectral bundle method for semidefinite programming. SIAM J. Optim. 10(3), 673\u2013696 (2000)","journal-title":"SIAM J. Optim."},{"key":"604_CR20","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1137\/0806020","volume":"6","author":"C Helmberg","year":"1996","unstructured":"Helmberg, C., Rendl, F., Vanderbei, R., Wolkowicz, H.: An interior point method for semidefinite programming. SIAM J. Optim. 6, 342\u2013361 (1996)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"604_CR21","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1093\/imanum\/22.3.329","volume":"22","author":"N Higham","year":"2002","unstructured":"Higham, N.: Computing a nearest symmetric correlation matrix-a problem from finance. IMA J. Numer. Anal. 22(3), 329\u2013343 (2002)","journal-title":"IMA J. Numer. Anal."},{"key":"604_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-02796-7","volume-title":"Convex Analysis and Minimization Algorithms","author":"J-B Hiriart-Urruty","year":"1993","unstructured":"Hiriart-Urruty, J.-B., Lemar\u00e9chal, C.: Convex Analysis and Minimization Algorithms. Springer, Heidelberg (1993). Two volumes"},{"issue":"2","key":"604_CR23","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/s10878-005-2269-7","volume":"10","author":"G J\u00e4ger","year":"2005","unstructured":"J\u00e4ger, G., Srivastav, A.: Improved approximation algorithms for maximum graph partitioning problems. J. Combin. Optim. 10(2), 133\u2013167 (2005)","journal-title":"J. Combin. Optim."},{"key":"604_CR24","first-page":"155","volume":"9","author":"JM Keil","year":"1991","unstructured":"Keil, J.M., Brecht, T.B.: The complexity of clustering in planar graphs. J. Comb. Math. Comb. Comput. 9, 155\u2013159 (1991)","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"604_CR25","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.1137\/S0097539705447037","volume":"36","author":"S Khot","year":"2005","unstructured":"Khot, S.: Ruling out ptas for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput. 36, 1025\u20131071 (2005)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"604_CR26","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1007\/s10107-006-0029-9","volume":"109","author":"M Ko\u010dvara","year":"2007","unstructured":"Ko\u010dvara, M., Stingl, M.: On the solution of large-scale sdp problems by the modified barrier method using iterative solvers. Math. Program. 109(2), 413\u2013444 (2007)","journal-title":"Math. Program."},{"key":"604_CR27","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/S0166-218X(01)00346-8","volume":"123","author":"J Krarup","year":"2002","unstructured":"Krarup, J., Pisinger, D., Plastria, F.: Discrete location problems with push-pull objectives. Discret. Appl. Math. 123, 363\u2013378 (2002)","journal-title":"Discret. Appl. Math."},{"key":"604_CR28","unstructured":"Lemar\u00e9chal C., Oustry F. (1999) Semidefinite relaxations and Lagrangian duality with application to combinatorial optimization. Research report 3710, INRIA"},{"issue":"1","key":"604_CR29","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/j.ipl.2008.03.016","volume":"108","author":"M Liazi","year":"2008","unstructured":"Liazi, M., Milis, I., Zissimopoulos, V.: A constant approximation algorithm for the densest k-subgraph problem on chordal graphs. Inf. Process. Lett. 108(1), 29\u201332 (2008)","journal-title":"Inf. Process. Lett."},{"key":"604_CR30","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. Inf. Theory IT 25, 1\u20137 (1979)","journal-title":"IEEE Trans. Inf. Theory IT"},{"issue":"1","key":"604_CR31","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1137\/S0895479802413856","volume":"26","author":"J Malick","year":"2004","unstructured":"Malick, J.: A dual approach to semidefinite least-squares problems. SIAM J. Matrix Anal. Appl. 26(1), 272\u2013284 (2004)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"4","key":"604_CR32","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1007\/s10898-007-9161-1","volume":"39","author":"J Malick","year":"2007","unstructured":"Malick, J.: Spherical constraint in Boolean quadratic programming. J. Glob. Optim. 39(4), 609\u2013622 (2007)","journal-title":"J. Glob. Optim."},{"issue":"1","key":"604_CR33","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1016\/j.endm.2010.05.051","volume":"36","author":"J Malick","year":"2010","unstructured":"Malick, J., Roupin, F.: Numerical study of SDP bounds for the $$k$$ -cluster problem. E. Notes Discret. Math. 36(1), 399\u2013406 (2010). Proceedings of ISCO 2010","journal-title":"E. Notes Discret. Math."},{"key":"604_CR34","unstructured":"Malick, J., Roupin, F.: On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds leading to newton-like methods. To appear in Math Programming B. http:\/\/hal.archives-ouvertes.fr\/hal-00662367 (2012)"},{"issue":"1","key":"604_CR35","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1137\/070704575","volume":"20","author":"J Malick","year":"2009","unstructured":"Malick, J., Povh, J., Rendl, F., Wiegele, A.: Regularization methods for semidefinite programming. SIAM J. Optim. 20(1), 336\u2013356 (2009)","journal-title":"SIAM J. Optim."},{"key":"604_CR36","unstructured":"Martin, A., Achterberg, T., Koch, T.: Branching rules revisited. Oper. Res. Lett. 33(1), 342\u2013354 (2005)"},{"key":"604_CR37","doi-asserted-by":"crossref","DOI":"10.1007\/b98874","volume-title":"Numerical Optimization","author":"J Nocedal","year":"1999","unstructured":"Nocedal, J., Wright, S.: Numerical Optimization. Springer, NY (1999)"},{"issue":"4","key":"604_CR38","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1137\/0604050","volume":"4","author":"Y Perl","year":"1983","unstructured":"Perl, Y., Shiloach, Y.: Efficient optimization of monotonic functions on trees. SIAM J. Algebr. Discret. Methods 4(4), 512\u2013516 (1983)","journal-title":"SIAM J. Algebr. Discret. Methods"},{"key":"604_CR39","doi-asserted-by":"crossref","first-page":"1380","DOI":"10.1016\/j.cor.2004.09.033","volume":"33","author":"D Pisinger","year":"2006","unstructured":"Pisinger, D.: Upper bounds and exact algorithms for p-dispersion problems. Comput. Oper. Res. 33, 1380\u20131398 (2006)","journal-title":"Comput. Oper. Res."},{"key":"604_CR40","unstructured":"Plateau, M.-C.: Reformulations quadratiques convexes pour la programmation quadratique en variables 0\u20131. PhD thesis, Conservatoire National des Arts et M\u00e9tiers (CNAM, Paris) (2006)"},{"key":"604_CR41","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1137\/050624509","volume":"28","author":"H Qi","year":"2006","unstructured":"Qi, H., Sun, D.: Quadratic convergence and numerical experiments of Newton\u2019s method for computing the nearest correlation matrix. SIAM J. Matrix Anal. Appl. 28, 360\u2013385 (2006)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"604_CR42","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/s10107-008-0235-8","volume":"121","author":"F Rendl","year":"2010","unstructured":"Rendl, F., Rinaldi, G., Wiegele, A.: Solving max-cut to optimality by intersecting semidefinite and polyedral relaxations. Math. Program. 121, 307\u2013335 (2010)","journal-title":"Math. Program."},{"key":"604_CR43","doi-asserted-by":"crossref","unstructured":"Roupin, F.: From linear to semidefinite programming: an algorithm to obtain semidefinite relaxations for bivalent quadratic problems. J. Comb. Optim. 8(4), 469\u2013493 (2004)","DOI":"10.1007\/s10878-004-4838-6"},{"key":"604_CR44","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1017\/S0962492901000071","volume":"10","author":"MJ Todd","year":"2001","unstructured":"Todd, M.J.: Semidefinite optimization. Acta Numer. 10, 515\u2013560 (2001)","journal-title":"Acta Numer."},{"key":"604_CR45","unstructured":"Tutuncu, R.H., Toh, K.C., Todd, M.J.: Inexact primal-dual path-following algorithms for a special class of convex quadratic SDP and related problems. Pac. J. Optim. 3(1), 135\u2013164 (2006)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-012-0604-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-012-0604-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-012-0604-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,5]],"date-time":"2019-07-05T00:08:20Z","timestamp":1562285300000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-012-0604-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10,26]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["604"],"URL":"https:\/\/doi.org\/10.1007\/s10107-012-0604-1","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,10,26]]}}}