{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:25Z","timestamp":1787337505581,"version":"build-2736575974"},"reference-count":27,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>\n                    Let G be a complete, weighted, undirected, bipartite graph with n red nodes, n\n                    <jats:sup>\"<\/jats:sup>\n                    blue nodes, and symmetric cost function c(x,y). A maximum matching for G consists of $\\min\\{n,n^\\prime\\}$ edges from distinct red nodes to distinct blue nodes. Our objective is to find a minimum-cost maximum matching, i.e., one for which the sum of the edge costs has minimal value. This is the weighted bipartite matching problem or, as it is sometimes called, the assignment problem. We report a new and very fast algorithm for an abstract special case of this problem. Our first requirement is that the nodes of the graph are given as a \"quasi-convex tour.\" This means that they are provided circularly ordered as x\n                    <jats:sub>1<\/jats:sub>\n                    ,...,x\n                    <jats:sub>N<\/jats:sub>\n                    , where N = n + n\n                    <jats:sup>\"<\/jats:sup>\n                    , and that for any $x_i, x_j, x_k, x_\\ell$, not necessarily adjacent but in tour order, with x\n                    <jats:sub>i<\/jats:sub>\n                    , x\n                    <jats:sub>j<\/jats:sub>\n                    of one color and $x_k,x_\\ell$ of the opposite color, the following inequality holds: \\[ c(x_i,x_\\ell) + c(x_j,x_k) \\le c(x_i,x_k) + c(x_j,x_\\ell). \\]\n                  <\/jats:p>\n                  <jats:p>If $n = n^\\prime$, our algorithm then finds a minimum-cost matching in $O(N \\log N)$ time. Given an additional condition of ``weak analyticity,\" the time complexity is reduced to $O(N)$. In both cases only linear space is required. In the special case where the circular ordering is a line-like ordering, these results apply even if $n \\ne n^\\prime$. Our algorithm is conceptually elegant, straightforward to implement, and free of large hidden constants. As such we expect that it may be of practical value in several problem areas. Many natural graphs satisfy the quasi-convexity condition. These include graphs which lie on a line or circle with the canonical tour ordering, and costs given by any concave-down function of arclength --- or graphs whose nodes lie on an arbitrary convex planar figure with costs provided by Euclidean distance. The weak-analyticity condition applies to points lying on a circle with costs given by Euclidean distance, and we thus obtain the first linear-time algorithm for the minimum-cost matching problem in this setting (and also where costs are given by the $L_1$ or $L_\\infty$ metrics). Given two symbol strings over the same alphabet, we may imagine one to be red and the other blue and use our algorithms to compute string distances. In this formulation, the strings are embedded in the real line and multiple independent assignment problems are solved, one for each distinct alphabet symbol. While these examples are somewhat geometrical, it is important to remember that our conditions are purely abstract; hence, our algorithms may find application to problems in which no direct connection to geometry is evident.<\/jats:p>","DOI":"10.1137\/s0097539794267243","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"170-201","source":"Crossref","is-referenced-by-count":11,"title":["Linear and Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours"],"prefix":"10.1137","volume":"27","author":[{"given":"Samuel R.","family":"Buss","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter N.","family":"Yianilos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, A. Bar\u2010Noy, S. Khuller, D. Kravets, and B. Schieber,\n                      Efficient minimum cost matching using quadrangle inequality\n                      , in Proc. 33rd Annual IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1992, pp. 583\u2013592.","DOI":"10.1109\/SFCS.1992.267793"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90124-U"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840359"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"A. Aggarwal and J. Park,\n                      Notes on searching in multidimensional monotone arrays\n                      , in Proc. 29th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1988, pp. 497\u2013512.","DOI":"10.1109\/SFCS.1988.21966"},{"key":"R5","unstructured":"S. R. Buss, K. G. Kanzelberger, D. Robinson, and P. N. Yianilos,\n                      Solving the Minimum\u2010cost Matching Problem for Quasi\u2010convex Tours: An Efficient ANSI\u2010C Implementation\n                      , Tech. Report CS94\u2010370, University of California, San Diego, 1994."},{"key":"R6","unstructured":"S. R. Buss and P. N. Yianilos,\n                      A Bipartite Matching Approach to Approximate String Comparison and Search\n                      , Tech. Report, NEC Research Institute, Princeton, NJ, 1995."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90031-9"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90101-1"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90215-J"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1287\/opre.12.5.655"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90143-6"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/0216043"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"A. Hoffman, On simple linear programming problems, Amer. Math. Soc., Providence, R.I., 1963, 317\u201332728:1007","DOI":"10.1090\/pspum\/007\/0157778"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90014-X"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0403009"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02090398"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90016-R"},{"key":"R18","unstructured":"E. Lawler,\n                      Combinatorial Optimization: Networks and Matroids\n                      , Holt, Rinehart and Winston, New York, 1976."},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195993000087"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0220026"},{"key":"R21","volume-title":"Time warps, string edits, and macromolecules: the theory and practice of sequence comparison","author":"Sankoff David","year":"1983"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/0218080"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90009-X"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90032-6"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1137\/0603055"},{"key":"R26","unstructured":"P. N. Yianilos,\n                      The Definition, Computation and Application of Symbol String Similarity Functions\n                      , Master\u2019s thesis, Emory University, Atlanta, GA, 1978."},{"key":"R27","unstructured":"P. N. Yianilos and S. R. Buss,\n                      Associative memory circuit system and method, continuation\u2010in\u2010part\n                      , U.S. Patent 4490811, 1984."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794267243","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:36Z","timestamp":1787336076000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794267243"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794267243"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794267243","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}