An Optimal Algorithm for Online Freeze-tag
From MaRDI portal
Publication:6313616
DOI10.4230/LIPICS.FUN.2021.8zbMATH Open1515.68381arXiv1902.01609MaRDI QIDQ6313616FDOQ6313616
Authors: Julian Wellman 
Publication date: 5 February 2019
Abstract: In the freeze-tag problem, one active robot must wake up many frozen robots. The robots are considered as points in a metric space, where active robots move at a constant rate and activate other robots by visiting them. In the (time-dependent) online variant of the problem, frozen robots are not revealed until a specified time. Hammar, Nilsson, and Persson have shown that no online algorithm can achieve a competitive ratio better than for online freeze-tag, and asked whether there is any -competitive algorithm. In this paper, we provide a -competitive algorithm for online time-dependent freeze-tag, and show that no algorithm can achieve a lower competitive ratio on every metric space.
Recommendations
- The Online Freeze-Tag Problem
- A Neighborhood Search Technique for the Freeze Tag Problem
- Analysis of Heuristics for the Freeze-Tag Problem
- An \(O(1)\)-approximation algorithm for the 2-dimensional geometric freeze-tag problem
- Trackless online algorithms for the server problem
- An optimal deterministic algorithm for online \(b\)-matching
- Online labeling: algorithms, lower bounds and open questions
- Algorithm Theory - SWAT 2004
- Tight lower bounds for the online labeling problem
- Tight lower bounds for the online labeling problem
Cited In (5)
This page was built for publication: An Optimal Algorithm for Online Freeze-tag
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6313616)
