Home Bookmarks Papers Blog

Approximation to the Weighted Minimum Matching

  1. Create randomized matching between points.
  2. Then iteratively improve it locally, until no further imrpovement is possible.
    1. In each iteration:
        For each pair of edges of the matching:
        checks if creating a new matching, by interchanging their endpoints, improves the matching weight.
        If so, we replace the old matching with thenew one.