God save the queen

Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Sunil Shende

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

Queen Daniela of Sardinia is asleep at the center of a round room at the top of the tower in her castle. She is accompanied by her faithful servant, Eva. Suddenly, they are awakened by cries of "Fire". The room is pitch black and they are disoriented. There is exactly one exit from the room somewhere along its boundary. They must find it as quickly as possible in order to save the life of the queen. It is known that with two people searching while moving at maximum speed 1 anywhere in the room, the room can be evacuated (i.e., with both people exiting) in 1 + 2π/3 + √3 ≈ 4.8264 time units and this is optimal [Czyzowicz et al., DISC'14], assuming that the first person to find the exit can directly guide the other person to the exit using her voice. Somewhat surprisingly, in this paper we show that if the goal is to save the queen (possibly leaving Eva behind to die in the fire) there is a slightly better strategy. We prove that this "priority" version of evacuation can be solved in time at most 4.81854. Furthermore, we show that any strategy for saving the queen requires time at least 3 + π/6 + v3/2 ~ 4.3896 in the worst case. If one or both of the queen's other servants (Biddy and/or Lili) are with her, we show that the time bounds can be improved to 3.8327 for two servants, and 3.3738 for three servants. Finally we show lower bounds for these cases of 3.6307 (two servants) and 3.2017 (three servants). The case of n > 4 is the subject of an independent study by Queen Daniela's Royal Scientific Team.

Original languageEnglish (US)
Title of host publication9th International Conference on Fun with Algorithms, FUN 2018
EditorsGiuseppe Prencipe, Hiro Ito, Stefano Leonardi, Linda Pagli
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages161-1620
Number of pages1460
ISBN (Electronic)9783959770675
DOIs
StatePublished - Jun 1 2018
Event9th International Conference on Fun with Algorithms, FUN 2018 - La Maddalena Island, Italy
Duration: Jun 13 2018Jun 15 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume100
ISSN (Print)1868-8969

Other

Other9th International Conference on Fun with Algorithms, FUN 2018
CountryItaly
CityLa Maddalena Island
Period6/13/186/15/18

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Algorithm
  • Disk
  • Evacuation
  • Exit
  • Priority
  • Queen
  • Robots
  • Search
  • Servants
  • Trajectory
  • Wireless communication

Fingerprint Dive into the research topics of 'God save the queen'. Together they form a unique fingerprint.

  • Cite this

    Czyzowicz, J., Georgiou, K., Killick, R., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., & Shende, S. (2018). God save the queen. In G. Prencipe, H. Ito, S. Leonardi, & L. Pagli (Eds.), 9th International Conference on Fun with Algorithms, FUN 2018 (pp. 161-1620). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 100). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.FUN.2018.16