Title
How to Whack Moles
Authors
-
Publication
K. Jansen and R. Solis-Oba (eds.): Approximation and
Online Algorithms, Lecture Notes in Computer Science
2909, pages 192-205, Springer, 2004.
Source
-
Classification
-
not available
Keywords
-
online traveling salesman problem, competitive
analysis, deterministic, complexity, dynamic
programming
-
-
In the classical whack-a-mole game moles that
pop up at certain locations must be whacked by means
of a hammer before they go under ground again. The
goal is to maximize the number of moles caught. This
problem can be formulated as an online optimization
problem: Requests (moles) appear over time at points
in a metric space and must be served (whacked) by a
server (hammer) before their deadlines (i.e., before
they disappear). An online algorithm learns each
request only at its release time and must base its
decisions on incomplete information. We study the
online whack-a-mole problem on the real line
and on the uniform metric space. While on the line
no deterministic algorithm can achieve a bounded
competitive ratio, we provide competitive algorithms
for the uniform metric space. Our online
investigations are complemented by complexity
results for the offline problem.
