Infinite linear programming and online searching with turn cost

DOI10.1016/J.TCS.2017.01.013zbMath1359.68320OpenAlexW2582579716MaRDI QIDQ515543

Diogo Arsénio, Spyros Angelopoulos, Christoph Dürr

Publication date: 16 March 2017

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

Full work available at URL: https://hal.sorbonne-universite.fr/hal-01452876/file/Angelopoulos_Infinite_linear.pdf

zbMATH Keywords

infinite linear programmingcompetitive analysis of online algorithmssearch and exploration problems

Mathematics Subject Classification ID

Linear programming (90C05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Online algorithms; streaming algorithms (68W27)

Related Items (10)

Further connections between contract-scheduling and ray-searching problems ⋮ Multi-processor search and scheduling problems with setup cost ⋮ Competitive search in a network ⋮ Best-of-both-worlds analysis of online search ⋮ Almost-Optimal Deterministic Treasure Hunt in Unweighted Graphs ⋮ Impact of knowledge on the cost of treasure hunt in trees ⋮ Weighted online search ⋮ Online search with a hint ⋮ Online failure diagnosis in interdependent networks ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
• Searching in the plane
• Duality in infinite dimensional linear programming
• The theory of search games and rendezvous.
• On-line parallel heuristics, processor scheduling and robot searching under the competitive framework
• Online searching with turn cost
• Searching on a line: a complete characterization of the optimal solution
• On the linear search problem
• Yet more on the linear search problem
• The search game on a network with immobile hider
• The Oil Searching Problem
• Hyperbolic Dovetailing
• Duality gaps in semi-infinite linear programming—an approximation problem
• Minimax Solutions for Linear Search Problems
• Optimal Constructions of Hybrid Algorithms
• The ultimate strategy to search on \(m\) rays?

This page was built for publication: Infinite linear programming and online searching with turn cost