A Randomized O(log2 k)-Competitive Algorithm for Metric Bipartite Matching

This publication has 16 references indexed in Scilit:

• Online matching on a line
  Theoretical Computer Science, 2005
• A tight bound on approximating arbitrary metrics by tree metrics
  Journal of Computer and System Sciences, 2004
• An optimal deterministic algorithm for online b-matching
  Theoretical Computer Science, 2000
• The Online Transportation Problem
  SIAM Journal on Discrete Mathematics, 2000
• On the k -server conjecture
  Journal of the ACM, 1995
• A General Approximation Technique for Constrained Forest Problems
  SIAM Journal on Computing, 1995
• On-line algorithms for weighted bipartite matching and stable marriages
  Theoretical Computer Science, 1994
• Searching in the Plane
  Information and Computation, 1993
• Online Weighted Matching
  Journal of Algorithms, 1993
• Competitive algorithms for server problems
  Journal of Algorithms, 1990