TY - GEN

T1 - The online metric matching problem for doubling metrics

AU - Gupta, Anupam

AU - Lewi, Kevin

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84883772355&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84883772355&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-31594-7_36

DO - 10.1007/978-3-642-31594-7_36

M3 - Conference contribution

AN - SCOPUS:84883772355

SN - 9783642315930

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 424

EP - 435

BT - Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings

T2 - 39th International Colloquium on Automata, Languages, and Programming, ICALP 2012

Y2 - 9 July 2012 through 13 July 2012

ER -