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 -