Advertisement
Published in:
01-01-2014
Online bottleneck matching
Published in: Journal of Combinatorial Optimization | Issue 1/2014
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
We consider the online bottleneck matching problem, where \(k\) server-vertices lie in a metric space and \(k\) request-vertices that arrive over time each must immediately be permanently assigned to a server-vertex. The goal is to minimize the maximum distance between any request and its server. Because no algorithm can have a competitive ratio better than \(O(k)\) for this problem, we use resource augmentation analysis to examine the performance of three algorithms: the naive Greedy algorithm, Permutation, and Balance. We show that while the competitive ratio of Greedy improves from exponential (when each server-vertex has one server) to linear (when each server-vertex has two servers), the competitive ratio of Permutation remains linear when an extra server is introduced at each server-vertex. The competitive ratio of Balance is also linear with an extra server at each server-vertex, even though it has been shown that an extra server makes it constant-competitive for the min-weight matching problem.