The online metric matching problem for doubling metrics

Anupam Gupta, Kevin Lewi

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In the online minimum-cost metric matching problem, we are given an instance of a metric space with k servers, and must match arriving requests to as-yet-unmatched servers to minimize the total distance from the requests to their assigned servers. We study this problem for the line metric and for doubling metrics in general. We give O(logk)-competitive randomized algorithms, which reduces the gap between the current O(log2 k)-competitive randomized algorithms and the constant-competitive lower bounds known for these settings. We first analyze the "harmonic" algorithm for the line, that for each request chooses one of its two closest servers with probability inversely proportional to the distance to that server; this is O(logk)-competitive, with suitable guess-and-double steps to ensure that the metric has aspect ratio polynomial in k. The second algorithm embeds the metric into a random HST, and picks a server randomly from among the closest available servers in the HST, with the selection based upon how the servers are distributed within the tree. This algorithm is O(1)-competitive for HSTs obtained from embedding doubling metrics, and hence gives a randomized O(logk)-competitive algorithm for doubling metrics.

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings
Number of pages12
EditionPART 1
StatePublished - 2012
Event39th International Colloquium on Automata, Languages, and Programming, ICALP 2012 - Warwick, United Kingdom
Duration: Jul 9 2012Jul 13 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume7391 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other39th International Colloquium on Automata, Languages, and Programming, ICALP 2012
Country/TerritoryUnited Kingdom

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'The online metric matching problem for doubling metrics'. Together they form a unique fingerprint.

Cite this