@inproceedings{aa6413dbb64841238f1d2d5d9b43f7d4,
title = "Online strategies for evacuating from a convex region in the plane",
abstract = "This paper studies an evacuation problem that evacuees inside an affected convex region in the plane try to escape to a boundary of the region as quickly as possible. The boundary information of the region is usually unknown to the evacuees at the beginning during an emergency. But with the help of helicopters or even satellite remote sensing technology, outside rescuers can easily get complete boundary information, and rescuers can share the information with evacuees once getting in touch with the evacuee who firstly reaches a boundary. For the scenario that people evacuate from several different positions, we first show that 3 is a lower bound on the competitive ratio, and presentpffiffi an online strategy with its competitive ratio proved to be no more than 2 {\th} 5. For the scenario that people evacuate from a single initial position, we present a strategy with its competitive ratio very close to the lower bound.",
keywords = "Competitive analysis, Convex region, Evacuation strategy",
author = "Songhua Li and Yinfeng Xu",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 11th International Frontiers of Algorithmics Workshop, FAW 2017 ; Conference date: 23-06-2017 Through 25-06-2017",
year = "2017",
doi = "10.1007/978-3-319-59605-1\_14",
language = "英语",
isbn = "9783319596044",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "151--162",
editor = "Frances Rosamond and Mingyu Xiao",
booktitle = "Frontiers in Algorithmics - 11th International Workshop, FAW 2017, Proceedings",
}