-
Title
-
Greedy Is Good: An Empirical Evaluation of Three
Algorithms for Online Bottleneck Matching
-
Creator
-
Anthony, Barbara M.
Harbour, Christine
King, Jordan
-
Date
-
February, 2019
-
Language
-
English
-
Publisher
-
Journal of Combinatorial Mathematics and Combinatorial Computing
-
Identifier
-
Anthony, Barbara, Harbour, Christine & King, Jordan. (2019) Greedy Is Good: An Empirical Evaluation of Three Algorithms for Online Bottleneck Matching. Journal of Combinatorial Mathematics and Combinatorial Computing. 108. 15-31
-
Subject
-
Online algorithms
Bottleneck matching
Resource augmentation
Approximation algorithms
-
Abstract
-
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 näıve GREEDY algorithm, as well as PERMUTATION, and 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, GREEDY frequently performs the best, and thus is recommended due to its simplicity.
