{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T03:26:14Z","timestamp":1778297174398,"version":"3.51.4"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Classif"],"published-print":{"date-parts":[[2009,12]]},"DOI":"10.1007\/s00357-009-9041-0","type":"journal-article","created":{"date-parts":[[2010,1,7]],"date-time":"2010-01-07T10:18:14Z","timestamp":1262859494000},"page":"279-296","source":"Crossref","is-referenced-by-count":12,"title":["Seriation in the Presence of Errors: NP-Hardness of l \u221e -Fitting Robinson Structures to Dissimilarity Matrices"],"prefix":"10.1007","volume":"26","author":[{"given":"Victor","family":"Chepoi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bernard","family":"Fichet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Morgan","family":"Seston","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,1,8]]},"reference":[{"key":"9041_CR1","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B ASPVAL","year":"1979","unstructured":"ASPVAL, B., PLASS, M.F., and TARJAN, R.E. (1979), \u201cA Linear Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas\u201d, Information Processing Letters, 8, 121\u2013123.","journal-title":"Information Processing Letters"},{"key":"9041_CR2","first-page":"1073","volume":"17","author":"R AGARWALA","year":"1999","unstructured":"AGARWALA, R., BAFNA, V., FARACH, M., NARAYANAN, B., PATERSON, M., and THORUP, M. (1999), \u201cOn the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)\u201d, SIAM Journal on Computing, 17, 1073\u20131085.","journal-title":"SIAM Journal on Computing"},{"key":"9041_CR3","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1137\/S0097539795285771","volume":"28","author":"JE ATKINS","year":"1998","unstructured":"ATKINS, J.E., BOMAN, E.G., and HENDRICKSON, B. (1998), \u201cA Spectral Algorithm for Seriation and the Consecutive Ones Problem\u201d, SIAM Journal on Computing, 28, 297\u2013310.","journal-title":"SIAM Journal on Computing"},{"key":"9041_CR4","unstructured":"B\u0102DOIU, M. (2003), \u201cApproximation Algorithm for Embedding Metrics into a Twodimensional Space\u201d, in Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore 2003, pp. 434\u2013443."},{"key":"9041_CR5","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/s00357-001-0014-1","volume":"18","author":"J-P BARTH\u00c9LEMY","year":"2001","unstructured":"BARTH\u00c9LEMY, J.-P. and BRUCKER, F. (2001), \u201cNP-hard Approximation Problems in Overlapping Clustering\u201d, Journal of Classification, 18, 159\u2013183.","journal-title":"Journal of Classification"},{"key":"9041_CR6","first-page":"70","volume":"206","author":"S BENZER","year":"1962","unstructured":"BENZER, S. (1962), \u201cThe Fine Structure of the Gene\u201d, Scientific American, 206, 70\u201384.","journal-title":"Scientific American"},{"key":"9041_CR7","unstructured":"BERRY, M.W., HENDRICKSON, B., and RAGHAVAN, P. (1996), \u201cSparse Matrix Reordering Schemes for Browsing Hypertext\u201d, in The Mathematics of Numerical Analysis, eds. J. Renegar, M. Shub, and S. Smale, Lectures in Applied Mathematics, Vol. 32, American Mathematical Society, pp. 99\u2013123."},{"key":"9041_CR8","first-page":"31","volume":"2","author":"P BERTRAND","year":"1985","unstructured":"BERTRAND, P. and DIDAY, E. (1985), \u201cA Visual Representation of the Compatibility Between an Order and a Dissimilarity Index: The Pyramids\u201d, Computational Statistics Quarterly, 2, 31\u201344.","journal-title":"Computational Statistics Quarterly"},{"key":"9041_CR9","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1023\/A:1009870418160","volume":"5","author":"N BLEUZEN-GUERNALEC","year":"2000","unstructured":"BLEUZEN-GUERNALEC, N. and COLMERAUER, A. (2000), \u201cOptimal Narrowing of a Block of Sortings in Optimal Time\u201d, Constraints, 5, 85\u2013118.","journal-title":"Constraints"},{"key":"9041_CR10","volume-title":"\u201cMod\u00e8les de Classification en Classes Empitantes\u201d, Th`ese","author":"F BRUCKER","year":"2001","unstructured":"BRUCKER, F. (2001), \u201cMod\u00e8les de Classification en Classes Empitantes\u201d, Th`ese, EHESS, Paris."},{"key":"9041_CR11","doi-asserted-by":"crossref","first-page":"1280","DOI":"10.1093\/bioinformatics\/bti141","volume":"21","author":"G CARAUX","year":"2005","unstructured":"CARAUX G. and PINLOCHE S. (2005), \u201cPermutMatrix: A Graphical Environment to Arrange Gene Expression Profiles in Optimal Linear Order\u201d, Bioinformatics, 21, 1280\u20131281.","journal-title":"Bioinformatics"},{"key":"9041_CR12","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/s003579900015","volume":"14","author":"V CHEPOI","year":"1997","unstructured":"CHEPOI, V. and FICHET, B. (1997), \u201cRecognition of Robinsonian Dissimilarities\u201d, Journal of Classification, 14, 311\u2013325.","journal-title":"Journal of Classification"},{"key":"9041_CR13","doi-asserted-by":"crossref","first-page":"600","DOI":"10.1006\/jmps.1999.1270","volume":"44","author":"V CHEPOI","year":"2000","unstructured":"CHEPOI, V. and FICHET, B. (2000), \u201cl\u221e-approximation via Subdominants\u201d, Journal of Mathematical Psychology, 44, 600\u2013616.","journal-title":"Journal of Mathematical Psychology"},{"key":"9041_CR14","unstructured":"CHEPOI, V. and SESTON M. (2007), \u201cSeriation in the Presence of Errors: An Approximation Algorithm for Fitting Robinson Structures to DissimilarityMatrices\u201d (submitted)."},{"key":"9041_CR15","series-title":"Lecture Notes in Statistics Vol. 93","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/978-1-4612-2686-4_2","volume-title":"Classification and Dissimilarity Analysis","author":"F CRITCHLEY","year":"1994","unstructured":"CRITCHLEY, F. and FICHET, B. (1994), \u201cThe Partial Order by Inclusion of the Principal Classes of Dissimilarities on a Finite Set, and Some of Their Basic Properties\u201d, in Classification and Dissimilarity Analysis, ed. B. van Cutsem, Lecture Notes in Statistics Vol. 93, New York: Springer-Verlag, pp. 5\u201365."},{"key":"9041_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-04295-9","volume-title":"Geometry of Cuts and Metrics","author":"M DEZA","year":"1997","unstructured":"DEZA, M. and LAURENT, M. (1997), Geometry of Cuts and Metrics, Berlin: Springer- Verlag."},{"key":"9041_CR17","first-page":"201","volume-title":"Multidimensional Data Analysis","author":"E DIDAY","year":"1986","unstructured":"DIDAY, E. (1986), \u201cOrders and Overlapping Clusters by Pyramids\u201d, in Multidimensional Data Analysis, eds. J. de Leeuw, W. Heiser, J. Meulman, and F. Critchley, Leiden: DSWO Press, pp. 201\u2013234."},{"key":"9041_CR18","first-page":"85","volume-title":"Classification and Related Methods of Data Analysis","author":"C DURAND","year":"1988","unstructured":"DURAND, C. and FICHET, B. (1988), \u201cOne\u2013to\u2013one Correspondences in Pyramidal Representation: A Unified Approach\u201d, in Classification and Related Methods of Data Analysis, ed. H.H. Bock, Amsterdam: North\u2013Holland, pp. 85\u201390."},{"key":"9041_CR19","unstructured":"DURAND, C. (1988), \u201cOrdre et Graphes Pseudo-Hierachiques: Th\u00b4eorie et Optimisation Algorithmique\u201d, Th`ese, Universit\u00b4e de Provence, Marseille."},{"key":"9041_CR20","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF01188585","volume":"13","author":"M FARACH","year":"1995","unstructured":"FARACH, M., KANNAN, S., and WARNOW, T. (1995), \u201cA Robust Model for Finding Optimal Evolutionary Trees\u201d, Algorithmica, 13, 155\u2013179.","journal-title":"Algorithmica"},{"key":"9041_CR21","first-page":"123","volume-title":"First World Congress of Bernoulli Society Proceedings, Vol.2","author":"B FICHET","year":"1986","unstructured":"FICHET B. (1986), \u201cData Analysis: Geometric and Algebraic Structures\u201d, in First World Congress of Bernoulli Society Proceedings, Vol.2, eds. Yu.A. Prohorov and V.V. Sazonov, Tashkent, USSR, Utrecht: VNU Science Press, pp. 123\u2013132."},{"key":"9041_CR22","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01830683","volume":"28","author":"D HALPERIN","year":"1994","unstructured":"HALPERIN, D. (1994), \u201cMusical Chronology by Seriation\u201d, Computers and the Humanities, 28, 13\u201318.","journal-title":"Computers and the Humanities"},{"key":"9041_CR23","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/S0196-6774(03)00083-X","volume":"49","author":"J H\u00c5STAD","year":"2003","unstructured":"H\u00c5STAD, J., IVANSSON, L., and LAGERGREN, J. (2003), \u201cFitting Points on the Real Line and Its Application to RH Mapping\u201d, Journal of Algorithms, 49, 42\u201362.","journal-title":"Journal of Algorithms"},{"key":"9041_CR24","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1111\/j.2044-8317.1974.tb00534.x","volume":"27","author":"LJ HUBERT","year":"1974","unstructured":"HUBERT, L.J. (1974), \u201cSome Applications of Graph Theory and Related Nonmetric Techniques to Problems of Approximate Seriation: The Case of Symmetric Proximity Measures\u201d, British Journal of Mathematical and Statistical Psychology, 27, 133\u2013153.","journal-title":"British Journal of Mathematical and Statistical Psychology"},{"key":"9041_CR25","doi-asserted-by":"crossref","first-page":"565","DOI":"10.2140\/pjm.1969.28.565","volume":"28","author":"DG KENDALL","year":"1969","unstructured":"KENDALL, D.G. (1969), \u201cIncidence Matrices, Interval Graphs and Seriation in Archaeology\u201d, Pacific Journal of Mathematics, 28, 565\u2013570.","journal-title":"Pacific Journal of Mathematics"},{"key":"9041_CR26","first-page":"417","volume-title":"Encyclopedia of Stastistical Sciences, Vol. 8","author":"DG KENDALL","year":"1982","unstructured":"KENDALL, D.G. (1982), \u201cSeriation\u201d, in Encyclopedia of Stastistical Sciences, Vol. 8, eds. S. Kotz and N.L. Johnson, New York: Wiley-Interscience, pp. 417\u2013424."},{"key":"9041_CR27","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02291398","volume":"36","author":"JC LINGOES","year":"1971","unstructured":"LINGOES J.C. (1971), \u201cSome Boundary Conditions for a Monotone Analysis of Symmetric Matrices\u201d, Psychometrika, 36, 195\u2013203.","journal-title":"Psychometrika"},{"key":"9041_CR28","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/B978-0-12-003101-6.50014-7","volume-title":"Advances in Archaeological Method and Theory, Vol. 1","author":"W MARQUARDT","year":"1978","unstructured":"MARQUARDT, W. (1978), \u201cAdvances in Archaeological Seriation\u201d, in Advances in Archaeological Method and Theory, Vol. 1, ed. M. Schiffer, New York: Academic Press, pp. 257\u2013314."},{"key":"9041_CR29","doi-asserted-by":"crossref","first-page":"3398","DOI":"10.1890\/05-0027","volume":"86","author":"I MIKLOS","year":"2005","unstructured":"MIKLOS, I., SOMODI, I., and PODANI, I. (2005), \u201cRearrangement of Ecological Data Matrices via Markov Chain Monte Carlo Simulation\u201d, Ecology, 86, 3398\u20133410.","journal-title":"Ecology"},{"key":"9041_CR30","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69280-2","volume-title":"Graphs and Genes","author":"B MIRKIN","year":"1984","unstructured":"MIRKIN, B. and RODIN, S. (1984), Graphs and Genes, Berlin: Springer-Verlag."},{"key":"9041_CR31","doi-asserted-by":"crossref","first-page":"293","DOI":"10.2307\/276978","volume":"16","author":"WS ROBINSON","year":"1951","unstructured":"ROBINSON, W.S. (1951), \u201cA Method for Chronologically Ordering Archaeological Deposits\u201d, American Antiquity, 16, 293\u2013301.","journal-title":"American Antiquity"},{"key":"9041_CR32","unstructured":"SAXE, J. B. (1979), \u201cEmbeddability of Weighted Graphs in k-space is Strongly NP-hard\u201d, in Proceedings of the 17th Allerton Conference on Communications, Control, and Computing, 1979, pp. 480\u2013489."},{"key":"9041_CR33","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1145\/800133.804350","volume-title":"Proceedings of the Tenth Annual ACM Symposium on Theory of computing, STOC\u201978","author":"TJ SCHAEFER","year":"1978","unstructured":"SCHAEFER, T.J. (1978), \u201cThe Complexity of Satisfiability Problems\u201d, in Proceedings of the Tenth Annual ACM Symposium on Theory of computing, STOC\u201978 New York: ACM Press, pp. 216\u2013226."},{"key":"9041_CR34","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics","author":"C SEMPLE","year":"2003","unstructured":"SEMPLE, C. and STEEL, M. (2003), Phylogenetics, Oxford: Oxford University Press."},{"key":"9041_CR35","volume-title":"Approximation Algorithms","author":"V VAZIRANI","year":"2001","unstructured":"VAZIRANI, V. (2001), Approximation Algorithms, Berlin: Springer."}],"container-title":["Journal of Classification"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00357-009-9041-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00357-009-9041-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00357-009-9041-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,22]],"date-time":"2024-03-22T15:18:41Z","timestamp":1711120721000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00357-009-9041-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["9041"],"URL":"https:\/\/doi.org\/10.1007\/s00357-009-9041-0","relation":{},"ISSN":["0176-4268","1432-1343"],"issn-type":[{"value":"0176-4268","type":"print"},{"value":"1432-1343","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12]]}}}