{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T18:10:18Z","timestamp":1787595018123,"version":"build-2736575974"},"reference-count":46,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>Seriation seeks to reconstruct a linear order between variables using unsorted, pairwise similarity information. It has direct applications in archeology and shotgun gene sequencing, for example. We write seriation as an optimization problem by proving the equivalence between the seriation and combinatorial 2-SUM problems on similarity matrices (2-SUM is a quadratic minimization problem over permutations). The seriation problem can be solved exactly by a spectral algorithm in the noiseless case, and we derive several convex relaxations for 2-SUM to improve the robustness of seriation solutions in noisy settings. These convex relaxations also allow us to impose structural constraints on the solution and hence solve semisupervised seriation problems. We derive new approximation bounds for some of these relaxations and present numerical experiments on archeological data, Markov chains, and DNA assembly from shotgun gene sequencing data.<\/jats:p>","DOI":"10.1137\/130947362","type":"journal-article","created":{"date-parts":[[2015,11,3]],"date-time":"2015-11-03T12:47:43Z","timestamp":1446554863000},"page":"1465-1488","source":"Crossref","is-referenced-by-count":17,"title":["Convex Relaxations for Permutation Problems"],"prefix":"10.1137","volume":"36","author":[{"given":"F.","family":"Fogel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"R.","family":"Jenatton","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"F.","family":"Bach","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"A.","family":"d'Aspremont","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,11,3]]},"reference":[{"key":"atypb1","first-page":"197","author":"Andersen E. D.","year":"2000","journal-title":"The Netherlands"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795285771"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1680020402"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.4310\/PAMQ.2006.v2.n4.a3"},{"key":"atypb5","unstructured":"D. Bertsekas,\n                      Nonlinear Programming\n                      , Athena Scientific, Belmont, MA, 1998."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00181-4"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9191-1"},{"key":"atypb8","unstructured":"T. M. Cover and J. A. Thomas,\n                      Elements of Information Theory\n                      , Wiley-Interscience, New York, 2012."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1120.0581"},{"key":"atypb10","first-page":"233","author":"Ding C.","year":"2004","journal-title":"Proceedings of the Twenty-First ACM International Conference on Machine Learning"},{"key":"atypb11","first-page":"17","volume":"5","author":"Erd\u00f6s P.","year":"1960","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/347476.347478"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1682"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.07.009"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800030109"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050052"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1965.15.835"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-010-0319-7"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/S089547989427470X"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0757-1"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver,\n                      Geometric Algorithms and Combinatorial Optimization\n                      , Springer, Berlin, 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"atypb22","unstructured":"F. R. Hodson,\n                      The La T\u00e8ne Cemetery at M\u00fcnsingen-Rain: Catalogue and Relative Chronology\n                      , Vol. 5, St\u00e4mpfli, Bern, Switzerland, 1968."},{"key":"atypb23","unstructured":"N. L. Johnson and S. Kotz,\n                      Distributions in Statistics: Continuous Multivariate Distributions\n                      , Wiley, New York, London, Sydney, 1972."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/BF00538862"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/0613066"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2014.12.009"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.9.4.586"},{"key":"atypb28","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1002\/sam.10071","volume":"3","author":"Liiv I.","year":"2010","journal-title":"Stat. Anal. Data Min."},{"key":"atypb29","first-page":"2168","author":"Lim C. H.","year":"2014","journal-title":"MA"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/0801013"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00078-X"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0033-0"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(99)00212-8"},{"key":"atypb34","unstructured":"Y. Nesterov,\n                      Global Quadratic Optimization via Conic Relaxation\n                      , CORE Discussion Paper 9860, Catholic University of Louvain, Louvain-la-Neuve, Belgium, 1998."},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"Y. Nesterov,\n                      Introductory Lectures on Convex Optimization\n                      , Kluwer Academic Publishers, Boston, MA, 2004.","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827593258280"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702413197"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.2307\/276978"},{"key":"atypb39","first-page":"23","volume":"19","author":"Sheppard W. F.","year":"1900","journal-title":"Trans. Cambridge Philos. Soc."},{"key":"atypb40","first-page":"1","volume":"25","author":"Shor N. Z.","year":"1987","journal-title":"Soviet J. Comput. Systems Sci."},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177703591"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0330-5"},{"key":"atypb43","unstructured":"G. W. Stewart and J. Sun,\n                      Matrix Perturbation Theory\n                      , Academic Press, Boston, MA, 1990."},{"key":"atypb44","doi-asserted-by":"crossref","unstructured":"N. Vuokko,\n                      Consecutive ones property and spectral ordering\n                      , in Proceedings of the 10th SIAM International Conference on Data Mining (SDM'10), 2010, pp. 350-360.","DOI":"10.1137\/1.9781611972801.31"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-005-4939-z"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009795911987"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130947362","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:57:42Z","timestamp":1787331462000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130947362"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":46,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/130947362"],"URL":"https:\/\/doi.org\/10.1137\/130947362","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}