Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-convex Tours

Abstract: Let G be a complete, weighted, undirected, bipartite graph with n red nodes, n' blue nodes, and symmetric cost function c(x,y). A maximum matching for G consists of min(n,n') 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,...,x_N where N = n + n', and that for any x_i, x_j, x_k, x_l, not necessarily adjacent but in tour order, with x_i,x_j of one color and x_k,x_l of the opposite color, the following inequality holds:

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.

Keywords: assignment problem, bipartite weighted matching, computational geometry, concave penalty function, convexity, linear time, Monge property, quadrangle inequality, string comparison.

• View the complete paper (converted to HTML)

• The complete paper (PDF)

• The complete paper (PostScript)

• BibTex entry

• My homepage ( Peter N. Yianilos )

• See also:
  • The LikeIt Intelligent String Comparison Facility
  • Netrics Corporation: The commercial source of the world's most advanced intelligent data quality solutions -- industrial-strength machine intelligence and learning technology for the international medical information processing industry, and others for whom database quality and robust operation is critical.
  • The LikeIt Intelligent String Comparison Facility (Software)
  • A Bipartite Matching Approach to Approximate String Comparison and Search
  • Solving the Minimum-Cost Matching Problem for Quasi-Convex Tours: An Efficient ANSI C Implementation
  • Quasi-Convex Matching (software)
  • Mulistage Intelligent String Comparison Method (patent pending)
  • Quasiconvex Bipartite Matching (patent pending)
  • The PF474 VLSI Chip
  • The Friendly Finder database utility
  • String comparator device system circuit and method (patent)
  • A dedicated compartor matches symbol strings fast and intelligently
  • String Comparator - A new tool for speech recognition
  • The application of a pattern matching algorithm to searching medical record text
  • The definition, computation, and application of symbol string similarity functions
  • PF474 Product Data Book

• Coauthors:
  • Sam Buss

The manuscript was completed in May of 1993 and was released as an NEC Research Institute Technical Report. report.