Journal article:
Samuel R. Buss, Peter N.
Yianilos.
"Linear and O(n log n) Time
Minimum-Cost Matching Algorithms for Quasiconvex Tours."
SIAM Journal on Computing 27 (1998) 170-201.
Download journal article version: postscript or PDF.
Also available:
A
software implementation (in ANSI C) & technical report.
Conference proceedings (earlier version).
Samuel R. Buss, Peter N.
Yianilos.
"Linear and O(n log n) Time
Minimum-Cost Matching Algorithms for Quasi-convex Tours (Extended
Abstract)."
Proceedings, Fifth Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA), 1994, pp. 65-76.
Download conference proceedings extended abstract: postscript or PDF.
The algorithm described in this paper is the subject of a patent co-owned by UCSD and NEC.:
Abstract: Let $G$ be a complete,
weighted, undirected, bipartite graph with $n$~red nodes, $n^\prime$~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_1,\ldots,x_N$ where $N = n + n^\prime$, and
that for any $x_i, x_j, x_k, x_\ell$, not necessarily adjacent but in tour
order, with $x_i,x_j$ 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)
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 Euclidian 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.
Download journal article version: postscript or PDF.