QCMATCH - Bipartite Matching for Quasi-Convex Tours
Technical report:
Samuel R. Buss, Kirk G. Kanzelberger, David
Robinson, Peter N. Yianilos.
"Solving the Minimum-Cost
Matching Principle for Quasi-Convex Tours: An Efficient ANSI C
Implementation."
Dept. of Computer Science Engineering,
UCSD, Technical report #370, April 1994, 69 pages.
Download technical report: postscript or PDF.
Software
qcmatch: An ANSI C Software Package for minimum-cost bipartite matching on quasi-convex tours. See the README file, or download the entire source code as a gzipped tar archive qcmatch.tar.gz or as a zip archive qcmatch.zip.
See also associated journal article:
This software uses a patented algorithm owned by UCSD and NEC.
Abstract from associated
journal article: 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.
Legalese
Permission to use, copy, modify and distribute any part of this qcmatch Program for educational, research and non-profit purposes, without fee, and without a written agreement is hereby granted, provided that the above copyright notice, this paragraph and the following three paragraphs appear in all copies.
Those desiring to incorporate this
IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS QCMATCH SOFTWARE , EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
THE QCMATCH SOFTWARE PROVIDED HEREIN IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. THE UNIVERSITY OF CALIFORNIA MAKES NO REPRESENTATIONS AND EXTENDS NO WARRANTIES OF ANY KIND, EITHER IMPLIED OR EXPRESS, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE, OR THAT THE USE OF THE QCMATCH SOFTWARE WILL NOT INFRINGE ANY PATENT, TRADEMARK OR OTHER RIGHTS.