direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 23-2003

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Title
How to Whack Moles
Authors
Publication
In K. Jansen and R. Solis-Oba (eds.): Approximation and Online Algorithms, Lecture Notes in Computer Science 2909, pages 192-205, Springer, 2004. A journal version is accepted for Theoretical Computer Science, to appear in 2005.
Classification
not available
Keywords
online traveling salesman problem, competitive analysis, deterministic, complexity, dynamic programming
Abstract
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.
Source
Download as [PDF] [ps.gz]

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe