### Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 11-22 |

Number of pages | 12 |

Journal | Theoretical Computer Science |

Volume | 670 |

DOIs | |

State | Published - Mar 29 2017 |

### Keywords

- Competitive analysis of online algorithms
- Infinite linear programming
- Search and exploration problems

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Infinite linear programming and online searching with turn cost'. Together they form a unique fingerprint.

## Cite this

*Theoretical Computer Science*,

*670*, 11-22. https://doi.org/10.1016/j.tcs.2017.01.013