Quasi-Convex Matching Software S. R. Buss, and K. G. Kanzelberger, and D. R. Robinson, and P. N. Yianilos This software implements the near linear time algorithms of Buss and Yianilos for solving a special class of bipartite weighted matching problems (assignment). Their paper "Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-convex Tours" appeared in SODA94, and will appear in Siam J. Computing. The software was first described in UCSD Technical Report CS94-370 entitled "Solving the Minimum-Cost Matching Problem for Quasi-Convex Tours: An Efficient ANSI C Implementation", by the four authors above. Description of Files: Makefile If you have gcc installed, you should be able to simply type make. Otherwise you will need to edit this file. qcmatch.c This is the main matching routine. It operates on pointers to graph vertices of unspecified type. The appropriate cost function, and Omega function (see the papers) are provided in seperate source files described below, and are linked with this module to form a complete system. It also includes an O(log n) time "generic" Omega implementation which may be used in cases where no constant time routine is available. The overall matching problem is then solved in O(n log n) time. qcmatch.h Defines the interface to qcmatch.c. qcarc.c qcsqrtarc.c qcsqrtline.c These files define three different settings. The first corresponds to graphs on a circle, with costs given by chord length, and might have been better named "qcchord.c". The second modifes this cost by taking its square root. The third corresponds to graphs on a line, with costs given by the sqrt of simple distance. The first and third include constant time Omega implementations so that the overall matching problem is solved in linear time. qctest.c This is the test driver program. It can generate random test problems of various types, and generate Postcript visualizations of their solutions. See runtests.csh below. It includes a dynamic programming (DP) algorithm (O(n^3) complexity) which is used to check the solutions generated by qcmatch.c. qcgrapharc.c qcgraphline.c These modules generate Postscript visualizations of the solutions to circular or linear matching problems respectively. They are linked with qctest.c. runtests.csh Run this after you've made the software. It starts by generating file "sample.ps" which depicts the solution to a random circular matching problem. Many instances of various problem types are then solved, and compared with the solution from a brute-force dynamic programming (DP) algorithm . You should examine the output to be sure that no failures are reported. Note however that the problems generated do not always have a unique solution. For this reason a success is defined as a matching which has the same cost as that found by the DP, even though the matching itself may differ. This is a rare event, but does occur, and the number of cases is reported by the script. Again, non zero counts do *not* indicate an error. qcarc.journal.c This is an alternative implementation of qcarc.c which corresponds more closely with the original Buss-Yianilos paper. It is included for purely didactic reasons and is not used. Changes since the UCSD Technical Report was issued: Makefile - "ranlib" line neutralized qctest.c - cpu_interval() timer function replaced with a more modern version (necessary to compile under Solaris) A bug was found in the released version of the qcmatch.c implementation, and fixed as follows: 359,362c359,362 NEW < M.d = (MNODE *) qc_match_malloc(3*(Max_node+1) * sizeof(MNODE)); < L = (LDEQUE *) qc_match_malloc(3 * sizeof(LDEQUE)); < L[0].d = (MNODE **) qc_match_malloc(3*(Max_node+1) * sizeof(MNODE *)); < L[2].d = (MNODE **) qc_match_malloc(3*(Max_node+1) * sizeof(MNODE *)); --- OLD > M.d = (MNODE *) qc_match_malloc(3 * Max_node * sizeof(MNODE)); > L = (LDEQUE *) qc_match_malloc(3 * sizeof(LDEQUE)); > L[0].d = (MNODE **) qc_match_malloc(3 * Max_node * sizeof(MNODE *)); > L[2].d = (MNODE **) qc_match_malloc(3 * Max_node * sizeof(MNODE *)); The allocation of all three deques requires one extra element, corresponding to the "imaginary" node used to fill out unbalanced subtours. Deques were overflowing for small Max_node and small unbalanced tours.