Faster Scaling Algorithms for General Graph Matching Problems.

摘要

This paper presents an algorithm for minimum cost matching on a general graph with integral edge costs, that runs in time close to the best known bound for cardinality matching. Specifically, let n, m and N denote the number of vertices, number of edges, and largest magnitude of a cost, respectively. Other applications of the new algorithm are given, including an efficient implementation of Christofides' traveling salesman approximation algorithm and efficient solutions to update problems that require the linear programming duals for matching. (KR)