Infinite linear programming and online searching with turn cost - Sorbonne Université
Article Dans Une Revue Theoretical Computer Science Année : 2017

Infinite linear programming and online searching with turn cost

Résumé

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. [TCS 2006] 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.
Fichier principal
Vignette du fichier
Angelopoulos_Infinite_linear.pdf (258.23 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01452876 , version 1 (02-02-2017)

Identifiants

Citer

Spyros Angelopoulos, Diogo Arsénio, Christoph Dürr. Infinite linear programming and online searching with turn cost. Theoretical Computer Science, 2017, ⟨10.1016/j.tcs.2017.01.013⟩. ⟨hal-01452876⟩
164 Consultations
175 Téléchargements

Altmetric

Partager

More