## Greedy Is Good: An Empirical Evaluation of Three Algorithms for Online Bottleneck Matching

### Item

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 näı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.