{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T02:52:08Z","timestamp":1781578328111,"version":"3.54.5"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,1,4]],"date-time":"2013-01-04T00:00:00Z","timestamp":1357257600000},"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":[[2013,8]]},"DOI":"10.1007\/s10107-012-0627-7","type":"journal-article","created":{"date-parts":[[2013,1,3]],"date-time":"2013-01-03T03:18:43Z","timestamp":1357183123000},"page":"77-97","source":"Crossref","is-referenced-by-count":32,"title":["Semidefinite relaxations of ordering problems"],"prefix":"10.1007","volume":"140","author":[{"given":"P.","family":"Hungerl\u00e4nder","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"F.","family":"Rendl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2013,1,4]]},"reference":[{"key":"627_CR1","first-page":"10","volume":"26","author":"H Achatz","year":"2006","unstructured":"Achatz, H., Kleinschmidt, P., Lambsdorff, J.: Der corruption perceptions index und das linear ordering problem. ORNews 26, 10\u201312 (2006)","journal-title":"ORNews"},{"issue":"1","key":"627_CR2","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/j.dam.2008.06.002","volume":"157","author":"ARS Amaral","year":"2009","unstructured":"Amaral, A.R.S.: A new lower bound for the single row facility layout problem. Discrete Appl. Math. 157(1), 183\u2013190 (2009)","journal-title":"Discrete Appl. Math."},{"key":"627_CR3","unstructured":"Amaral, A.R.S., Letchford, A.N.: A polyhedral approach to the single row facility layout problem (in preparation). Preprint available from http:\/\/www.optimization-online.org\/DB_FILE\/2008\/03\/1931.pdf (2011)"},{"issue":"2","key":"627_CR4","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/j.disopt.2005.03.001","volume":"2","author":"MF Anjos","year":"2005","unstructured":"Anjos, M.F., Kennings, A., Vannelli, A.: A semidefinite optimization approach for the single-row layout problem with unequal dimensions. Discrete Optim. 2(2), 113\u2013122 (2005)","journal-title":"Discrete Optim."},{"issue":"4","key":"627_CR5","doi-asserted-by":"crossref","first-page":"611","DOI":"10.1287\/ijoc.1080.0270","volume":"20","author":"MF Anjos","year":"2008","unstructured":"Anjos, M.F., Vannelli, A.: Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes. INFORMS J. Comput. 20(4), 611\u2013617 (2008)","journal-title":"INFORMS J. Comput."},{"issue":"4","key":"627_CR6","doi-asserted-by":"crossref","first-page":"805","DOI":"10.1080\/10556780902917735","volume":"24","author":"MF Anjos","year":"2009","unstructured":"Anjos, M.F., Yen, G.: Provably near-optimal solutions for very large single-row facility layout problems. Optim. Methods Softw. 24(4), 805\u2013817 (2009)","journal-title":"Optim. Methods Softw."},{"key":"627_CR7","unstructured":"Boenchendorf, K.: Reihenfolgenprobleme\/Mean-flow-time sequencing. Mathematical Systems in Economics 74. Verlagsgruppe Athenaum, Hain, Scriptor (1982)"},{"key":"627_CR8","unstructured":"Buchheim, C., Wiegele, A., Zheng, L.: Exact algorithms for the quadratic linear ordering problem. INFORMS J. Comput. 22(1), 168\u2013177 (2009)"},{"key":"627_CR9","unstructured":"Caprara, A., Jung M., Oswald, M., Reinelt, G., Traversi, E.: A betweenness approach for solving the linear arrangement problem. Technical report, University of Heidelberg (2011, in preparation)"},{"issue":"1","key":"627_CR10","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1287\/ijoc.1100.0390","volume":"23","author":"A Caprara","year":"2011","unstructured":"Caprara, A., Letchford, A.N., Salazar-Gonzalez, J.-J.: Decorous lower bounds for minimum linear arrangement. INFORMS J. Comput. 23(1), 26\u201340 (2011)","journal-title":"INFORMS J. Comput."},{"key":"627_CR11","doi-asserted-by":"crossref","first-page":"487","DOI":"10.2307\/1907514","volume":"26","author":"H Chenery","year":"1958","unstructured":"Chenery, H., Watanabe, T.: International comparisons of the structure of production. Econometrica 26, 487\u2013521 (1958)","journal-title":"Econometrica"},{"key":"627_CR12","doi-asserted-by":"crossref","unstructured":"Chimani, M., Hungerl\u00e4nder, P., J\u00fcnger, M., Mutzel, P.: An SDP approach to multi-level crossing minimization. In: Proceedings of Algorithm Engineering & Experiments [ALENEX\u20192011] (2011)","DOI":"10.1137\/1.9781611972917.12"},{"key":"627_CR13","doi-asserted-by":"crossref","unstructured":"Christof, T., Oswald, M., Reinelt, G.: Consecutive ones and a betweenness problem in computational biology. In: Proceedings of the 6th Conference on Integer Programming and Combinatorial Optimization (IPCO 1998). Lecture Notes in Computer Science, vol. 1412, pp. 213\u2013228. Springer, Berlin (1998)","DOI":"10.1007\/3-540-69346-7_17"},{"key":"627_CR14","unstructured":"Duff, I.S., Grimes, R.G., Lewis, J.G.: Users\u2019 Guide for the Harwell-Boeing Sparse Matrix Collection. Technical report, CERFACS, Toulouse, France (1992)"},{"key":"627_CR15","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/s10107-005-0661-9","volume":"105","author":"I Fischer","year":"2006","unstructured":"Fischer, I., Gruber, G., Rendl, F., Sotirov, R.: Computational experience with a bundle method for semidefinite cutten plane relaxations of max-cut and equipartition. Math. Program. 105, 451\u2013469 (2006)","journal-title":"Math. Program."},{"key":"627_CR16","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified np-complete problems. In: STOC \u201974: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pp. 47\u201363, New York (1974)","DOI":"10.1145\/800119.803884"},{"key":"627_CR17","doi-asserted-by":"crossref","first-page":"1190","DOI":"10.1287\/mnsc.20.8.1190","volume":"20","author":"F Glover","year":"1974","unstructured":"Glover, F., Klastorin, T., Klingman, D.: Optimal weighted ancestry relationships. Manag. Sci. 20, 1190\u20131193 (1974)","journal-title":"Manag. Sci."},{"key":"627_CR18","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M Goemans","year":"1995","unstructured":"Goemans, M., Williamson, D.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115\u20131145 (1995)","journal-title":"J. ACM"},{"issue":"6","key":"627_CR19","doi-asserted-by":"crossref","first-page":"1195","DOI":"10.1287\/opre.32.6.1195","volume":"32","author":"M Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel, M., J\u00fcnger, M., Reinelt, G.: A cutting plane algorithm for the linear ordering problem. Oper. Res. 32(6), 1195\u20131220 (1984)","journal-title":"Oper. Res."},{"issue":"1","key":"627_CR20","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1137\/0112012","volume":"12","author":"LH Harper","year":"1964","unstructured":"Harper, L.H.: Optimal assignments of numbers to vertices. SIAM J. Appl. Math. 12(1), 131\u2013135 (1964)","journal-title":"SIAM J. Appl. Math."},{"key":"627_CR21","doi-asserted-by":"crossref","unstructured":"Healy, P., Kuusik, A.: The vertex-exchange graph: a new concept for multilevel crossing minimisation. In: Proceedings of the Symposium on Graph Drawing [GD\u201999], pp. 205\u2013216. Springer, Berlin (1999)","DOI":"10.1007\/3-540-46648-7_21"},{"issue":"3","key":"627_CR22","doi-asserted-by":"crossref","first-page":"952","DOI":"10.1137\/S089547989631442X","volume":"21","author":"C Helmberg","year":"2000","unstructured":"Helmberg, C.: Fixing variables in semidefinite relaxations. SIAM J. Matrix Anal. Appl. 21(3), 952\u2013969 (2000)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"627_CR23","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1080\/03081089508818381","volume":"39","author":"C Helmberg","year":"1995","unstructured":"Helmberg, C., Mohar, B., Poljak, S., Rendl, F.: A spectral approach to bandwidth and separator problems in graphs. Linear Multilinear Algebra 39, 73\u201390 (1995)","journal-title":"Linear Multilinear Algebra"},{"key":"627_CR24","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":"2","key":"627_CR25","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1287\/opre.36.2.258","volume":"36","author":"SS Heragu","year":"1988","unstructured":"Heragu, S.S., Kusiak, A.: Machine layout problem in flexible manufacturing systems. Oper. Res. 36(2), 258\u2013268 (1988)","journal-title":"Oper. Res."},{"key":"627_CR26","doi-asserted-by":"crossref","unstructured":"Hiriart-Urruty, J.-B., Lemarechal, C.: Convex Analysis and Minimization Algorithms (vol. 1 and 2). Springer, Berlin (1993)","DOI":"10.1007\/978-3-662-02796-7_1"},{"key":"627_CR27","unstructured":"Hungerl\u00e4nder, P.: Semidefinite Approaches to Ordering Problems. PhD thesis, Alpen-Adria Universit\u00e4t Klagenfurt (2012)"},{"key":"627_CR28","doi-asserted-by":"crossref","unstructured":"Hungerl\u00e4nder, P., Rendl, F.: A computational study and survey of methods for the single-row facility layout problem. Comput. Optim. Appl. (2012, accepted)","DOI":"10.1007\/s10589-012-9505-8"},{"key":"627_CR29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00001","volume":"1","author":"M J\u00fcnger","year":"1997","unstructured":"J\u00fcnger, M., Mutzel, P.: 2-Layer straightline crossing minimization: performance of exact and heuristic algorithms. J. Graph Algorithms Appl. 1, 1\u201325 (1997)","journal-title":"J. Graph Algorithms Appl."},{"issue":"2","key":"627_CR30","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0166-218X(92)90229-4","volume":"36","author":"M Juvan","year":"1992","unstructured":"Juvan, M., Mohar, B.: Optimal linear labelings and eigenvalues of graphs. Discrete Appl. Math. 36(2), 153\u2013168 (1992)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"627_CR31","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/0377-2217(81)90005-9","volume":"8","author":"R Kaas","year":"1981","unstructured":"Kaas, R.: A branch and bound algorithm for the acyclic subgraph problem. Eur. J. Oper. Res. 8(4), 355\u2013362 (1981)","journal-title":"Eur. J. Oper. Res."},{"key":"627_CR32","volume-title":"The Stanford GraphBase: A Platform for Combinatorial Computing","author":"DE Knuth","year":"1993","unstructured":"Knuth, D.E.: The Stanford GraphBase: A Platform for Combinatorial Computing. ACM, New York (1993)"},{"key":"627_CR33","unstructured":"Leontief, W.: Quantitative input-output relations in the economic system of the united states. Rev. Econ. Stat. 18(3), 105\u2013125 (1936)"},{"key":"627_CR34","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions and 0\u20131 optimization. SIAM J. Optim. 1, 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"key":"627_CR35","unstructured":"Mart, R., Reinelt, G., Duarte, A.: A benchmark library and a comparison of heuristic methods for the linear ordering problem. Comput. Optim. Appl. 51(3), 1\u201321 (2011)"},{"issue":"3","key":"627_CR36","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1016\/S0166-218X(02)00397-9","volume":"127","author":"R Mart\u00ed","year":"2003","unstructured":"Mart\u00ed, R., Laguna, M.: Heuristics and meta-heuristics for 2-layer straight line crossing minimization. Discrete Appl. Math. 127(3), 665\u2013678 (2003)","journal-title":"Discrete Appl. Math."},{"key":"627_CR37","doi-asserted-by":"crossref","unstructured":"Mitchell, J.E., Borchers, B.: Solving linear ordering problems with a combined interior pointsimplex cutting plane algorithm. In: Frenk, T.T.H., Roos, K., Zhang, S. (eds.) High Performance Optimization, pp. 349\u2013366. Kluwer, Dordrecht (2000)","DOI":"10.1007\/978-1-4757-3216-0_14"},{"key":"627_CR38","doi-asserted-by":"crossref","unstructured":"Newman, A.: Cuts and orderings: on semidefinite relaxations for the linear ordering problem. In: Jansen, K., Khanna, S., Rolim, J., Ron, D. (eds.) Lecture Notes in Computer Science, vol. 3122, pp. 195\u2013206. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-27821-4_18"},{"key":"627_CR39","unstructured":"Schwarz, R.: A Branch-and-Cut Algorithm with Betweenness Variables for the Linear Arrangement Problems. Diploma thesis, Heidelberg (2010)"},{"issue":"3","key":"627_CR40","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"HD Sherali","year":"1990","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. Discrete Math. 3(3), 411\u2013430 (1990)","journal-title":"SIAM J. Discrete Math."},{"key":"627_CR41","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1287\/opre.17.5.812","volume":"17","author":"DM Simmons","year":"1969","unstructured":"Simmons, D.M.: One-dimensional space allocation: an ordering algorithm. Oper. Res. 17, 812\u2013826 (1969)","journal-title":"Oper. Res."},{"issue":"1","key":"627_CR42","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0012-365X(90)90056-N","volume":"79","author":"CD Simone","year":"1990","unstructured":"Simone, C.D.: The cut polytope and the Boolean quadric polytope. Discrete Math. 79(1), 71\u201375 (1990)","journal-title":"Discrete Math."},{"key":"627_CR43","unstructured":"Sturm, J.: Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones (updated for version 1.05). Available under http:\/\/sedumi.ie.lehigh.edu (2001)"},{"issue":"2","key":"627_CR44","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1109\/TSMC.1981.4308636","volume":"11","author":"K Sugiyama","year":"1981","unstructured":"Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst. Man Cybern. 11(2), 109\u2013125 (1981)","journal-title":"IEEE Trans. Syst. Man Cybern."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-012-0627-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-012-0627-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-012-0627-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,7]],"date-time":"2019-07-07T17:27:00Z","timestamp":1562520420000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-012-0627-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,4]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,8]]}},"alternative-id":["627"],"URL":"https:\/\/doi.org\/10.1007\/s10107-012-0627-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1,4]]}}}