کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
439358 690530 2006 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
How to whack moles
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
How to whack moles
چکیده انگلیسی

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 whacked. 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 (WHAM) on the real line and on the uniform metric space. While on the line no deterministic algorithm can achieve a constant competitive ratio, we provide competitive algorithms for the uniform metric space. Our online investigations are complemented by complexity results for the offline problem.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 361, Issues 2–3, 1 September 2006, Pages 329-341