Online searching with turn cost

DOI10.1016/j.tcs.2006.05.018zbMath1097.68031arXivcs/0406045OpenAlexW1995434882MaRDI QIDQ2503358

Erik D. Demaine, Sándor P. Fekete, Shmuel Gal

Publication date: 14 September 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0406045

zbMATH Keywords

search games competitive ratio online problems randomized strategies star search turn cost cow-path problem infinite linear programs linear-search problem

Mathematics Subject Classification ID

Searching and sorting (68P10) Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Linear Search with Terrain-Dependent Speeds ⋮ Further connections between contract-scheduling and ray-searching problems ⋮ Evacuating from \(\ell_p\) unit disks in the wireless model (extended abstract) ⋮ Multi-processor search and scheduling problems with setup cost ⋮ Online routing and searching on graphs with blocked edges ⋮ The ANTS problem ⋮ A general framework for searching on a line ⋮ Pebble guided optimal treasure hunt in anonymous graphs ⋮ Competitive search in a network ⋮ Evacuating two robots from multiple unknown exits in a circle ⋮ Best-of-both-worlds analysis of online search ⋮ Almost-Optimal Deterministic Treasure Hunt in Unweighted Graphs ⋮ Evacuating from \(\ell_p\) unit disks in the wireless model ⋮ Impact of knowledge on the cost of treasure hunt in trees ⋮ The beachcombers' problem: walking and searching with mobile robots ⋮ Search on a Line by Byzantine Robots ⋮ Weighted online search ⋮ Overcoming probabilistic faults in disoriented linear search ⋮ Optimal circle search despite the presence of faulty robots ⋮ Search Games: A Review ⋮ Algorithms for \(p\)-Faulty Search on a half-line ⋮ Online search with a hint ⋮ Deterministic treasure hunt in the plane with angular hints ⋮ Priority evacuation from a disk: the case of \(n \geq 4\) ⋮ Online algorithms for searching and exploration in the plane ⋮ Treasure evacuation with one robot on a disk ⋮ Multi-target ray searching problems ⋮ Online failure diagnosis in interdependent networks ⋮ Network search games with immobile hider, without a designated searcher starting point ⋮ Lower bounds for searching robots, some faulty ⋮ The expanding search ratio of a graph ⋮ Infinite linear programming and online searching with turn cost ⋮ Linear search by a pair of distinct-speed robots ⋮ Search on a line with faulty robots ⋮ Online searching with an autonomous robot ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Wireless evacuation on \(m\) rays with \(k\) searchers ⋮ Beachcombing on strips and islands ⋮ A General Framework for Searching on a Line ⋮ Byzantine fault tolerant symmetric-persistent circle evacuation ⋮ Time-energy tradeoffs for evacuation by two robots in the wireless model ⋮ Linear rendezvous with asymmetric clocks ⋮ Competitive Searching for a Line on a Line Arrangement. ⋮ Energy Consumption of Group Search on a Line ⋮ Polygon exploration with time-discrete vision ⋮ Search for an immobile hider in a known subset of a network ⋮ Approximations of Countably Infinite Linear Programs over Bounded Measure Spaces ⋮ Weighted group search on a line \& implications to the priority evacuation problem ⋮ A Simplex Method for Countably Infinite Linear Programs ⋮ Pebble guided near optimal treasure hunt in anonymous graphs

Uses Software

CPLEX

Cites Work