Online bottleneck matching

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.