How to Whack Moles

dc.contributor.authorKrumke, Sven O.
dc.contributor.authorMegow, Nicole
dc.contributor.authorVredeveld, Tjark
dc.date.accessioned2021-12-17T10:05:35Z
dc.date.available2021-12-17T10:05:35Z
dc.date.issued2003
dc.description.abstractIn 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.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15496
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14269
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.otheronline traveling salesman problemen
dc.subject.othercompetitive analysisen
dc.subject.otherdeterministicen
dc.subject.othercomplexityen
dc.subject.otherdynamic programmingen
dc.titleHow to Whack Molesen
dc.typeResearch Paperen
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften>Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2003, 23en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
Files
Original bundle
Now showing 1 - 2 of 2
Loading…
Thumbnail Image
Name:
Report-023-2003.pdf
Size:
163.56 KB
Format:
Adobe Portable Document Format
Description:
Loading…
Thumbnail Image
Name:
Report-023-2003.ps.gz
Size:
173.7 KB
Format:
Unknown data format
Description:
Collections