Solving the Minimum-Cost Matching Problem for Quasi-Convex Tours: An Efficient ANSI C Implementation

Abstract: We report an efficient and highly portable ANSI C implementation of the Buss-Yianilos minimum-cost matching algorithm for quasi-convex tours. A generic O(log n) time implementation of the required Omega predicate is included, resulting in worst-case O(n log n) runtime for arbitrary cost functions.

A constant-time Omega is provided for two special cases: the circle under Euclidean distance, and the real line where cost is defined as the square root of interpoint distance. In both of these settings, runtime is then O(n).

Code is also provided for circular tours with cost defined as the square root of angular distance (arclength). In this case, the generic Omega computation is employed.

The test programs generate pseudorandom node patterns. To ensure correctness, a straightforward O(n^3) dynamic programming solution may be optionally enabled, and the test programs will compare its result with that of the Buss-Yianilos algorithm.

As an additional option, the test programs produce PostScript-form graphical representations of the minimum-cost matchings found.

The performance of the package is reported for several modern RISC processors.

• The complete paper (PDF)

• The complete paper (PostScript)

• BibTex entry

• My homepage ( Peter N. Yianilos )

• See also:
  • Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-convex Tours
  • 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
  • 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
  • Kirk Kanzelberger
  • Dave Robinson