Have been remiss in blogging activities for the past few days. Have been recovering from severe cat-shock :)
And now for something completely different, from the SoCG preview file...
A matching in a graph is a set of disjoint edges (i.e no two sharing an endpoint) connecting pairs of vertices, and a maximum matching is a matching of maximum size. A perfect matching is one in which every vertex is the endpoint of some edge in the matching, and a min-cost perfect matching is a perfect matching of minimum weight (when weights are associated with each edge).
In the geometric setting, nodes are points in the Euclidean plane, and edges are weighted by the (Euclidean) distance between the corresponding pair of points (in general, there is an edge between any two points). Computing a Euclidean matching pairs up vertices to minimize the sum of distance between these pairs. A red-blue matching is the geometric analogue of bipartite matching in graphs; match up red and blue vertices in pairs to minimize the total cost (= sum of distances).
In contrast with general graphs, a rather peculiar state of affairs has been the case with geometric matching. Namely, red-blue matching appeared harder to solve than the monochromatic variant. In fact, there is a linear time approximation algorithm due to Pankaj Agarwal and Kasturi Varadarajan for estimating a min-cost matching in the plane, but the best such algorithm for red-blue matching ran in time O(n3/2).
Pankaj and Kasturi have a new result in the upcoming SoCG that improves matters significantly. Although a linear-time approximaton scheme for red-blue matching is still an open problem, they present an algorithm that computes an O(log(1/e))-approximation in time n1+e.
No comments:
Post a Comment