Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14269
For citation please use:
Main Title: How to Whack Moles
Author(s): Krumke, Sven O.
Megow, Nicole
Vredeveld, Tjark
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15496
http://dx.doi.org/10.14279/depositonce-14269
License: http://rightsstatements.org/vocab/InC/1.0/
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.
Subject(s): online traveling salesman problem
competitive analysis
deterministic
complexity
dynamic programming
Issue Date: 2003
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2003, 23
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-023-2003.pdf
Format: Adobe PDF | Size: 163.56 kB
DownloadShow Preview
Thumbnail
Report-023-2003.ps.gz
Format: Unknown | Size: 173.7 kB
Download

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.