@inproceedings{856992557ac446c6ac007e19aab869e3,
title = "The multi-source beachcombers{\textquoteright} problem",
abstract = "The Beachcombers{\textquoteright} Problem (c.f. [1]) is an optimization problem in which a line segment is to be searched by a set of mobile robots, where each robot has a searching speed si and a walking speed wi, such that si < wi. We explore a natural generalization of the Beachcombers{\textquoteright} Problem, the t-Source Beachcombers{\textquoteright} Problem (t-SBP), where the robots are not constrained to start at a single source: Consider n mobile robots labelled 1, 2,..., n. We choose t sources and we assign each robot to one of them. The problem is to choose the sources and develop mobility schedules (algorithms) for the robots which maximizes the speed of the fleet, or minimize the time that the robots need to collectively search the domain. We propose several algorithms for solving problems of this nature. We prove that 2-SBP is NP-hard even when the robots have identical walking speeds. This contrasts with the case when the robots have identical search speeds, where we give a polynomial time algorithm for t-SBP. We also give a 0.5569-approximation for 2-SBP with arbitrary walking and searching speeds. For t-SBP with arbitrary walking and searching speeds, we give an oblivious randomized algorithm and prove that it provides an expected 1−1/e approximation, asymptotically in t.",
keywords = "Algorithm, Approximation, Mobile robots, Partitioning, Randomized, Schedule, Searching, Segment, Speed, Walking",
author = "Jurek Czyzowicz and Leszek G{\c a}sieniec and Konstantinos Georgiou and Evangelos Kranakis and Fraser MacQuarrie",
note = "Funding Information: J. Czyzowicz and E. Kranakis—Research supported in part by NSERC Discovery grant. Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2015.; 10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2014 ; Conference date: 12-09-2014 Through 12-09-2014",
year = "2015",
doi = "10.1007/978-3-662-46018-4_1",
language = "English (US)",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "3--21",
editor = "Jie Gao and Fekete, {S{\'a}ndor P.} and Alon Efrat and Yanyong Zhang",
booktitle = "Algorithms for Sensor Systems - 10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2014, Revised Selected Papers",
}