TY - JOUR
T1 - Infinite linear programming and online searching with turn cost
AU - Angelopoulos, Spyros
AU - Arsénio, Diogo
AU - Dürr, Christoph
N1 - Publisher Copyright:
© 2017 Elsevier B.V.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.
PY - 2017/3/29
Y1 - 2017/3/29
N2 - We consider the problem of searching for a hidden target in an environment that consists of a set of concurrent rays. Every time the searcher turns direction, it incurs a fixed cost. The objective is to derive a search strategy for locating the target as efficiently as possible, and the performance of the strategy is evaluated by means of the well-established competitive ratio. In this paper we revisit an approach due to Demaine et al. [8] based on infinite linear-programming formulations of this problem. We first demonstrate that their definition of duality in infinite LPs can lead to erroneous results. We then provide a non-trivial correction which establishes the optimality of a certain round-robin search strategy.
AB - We consider the problem of searching for a hidden target in an environment that consists of a set of concurrent rays. Every time the searcher turns direction, it incurs a fixed cost. The objective is to derive a search strategy for locating the target as efficiently as possible, and the performance of the strategy is evaluated by means of the well-established competitive ratio. In this paper we revisit an approach due to Demaine et al. [8] based on infinite linear-programming formulations of this problem. We first demonstrate that their definition of duality in infinite LPs can lead to erroneous results. We then provide a non-trivial correction which establishes the optimality of a certain round-robin search strategy.
KW - Competitive analysis of online algorithms
KW - Infinite linear programming
KW - Search and exploration problems
UR - http://www.scopus.com/inward/record.url?scp=85011627824&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85011627824&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2017.01.013
DO - 10.1016/j.tcs.2017.01.013
M3 - Article
AN - SCOPUS:85011627824
VL - 670
SP - 11
EP - 22
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -