Menu
We empirically evaluate the performance of three approximation algorithms for the online bottleneck matching problem. In this matching problem, \( 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 assigned server. We consider the naïve \textsc{Greedy} algorithm, as well as \textsc{Permutation} and \textsc{Balance}, each of which were constructed to counter certain challenges in the online problem. We analyze the performance of each algorithm on a variety of data sets, considering each both in the original model, where applicable, and in the resource augmentation setting when an extra server is introduced at each server-vertex. While no algorithm strictly dominates, \textsc{Greedy} frequently performs the best, and thus is recommended due to its simplicity.