scientific article; zbMATH DE number 2102754

zbMath1045.90532MaRDI QIDQ4818841

Elias Koutsoupias, Mihalis Yannakakis, Christos H. Papadimitriou

Publication date: 24 September 2004

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

On the approximation of shortest escape paths ⋮ Exact algorithms for the minimum latency problem ⋮ Polynomial time algorithms for some minimum latency problems ⋮ Approximation and complexity of multi-target graph search and the Canadian traveler problem ⋮ Further connections between contract-scheduling and ray-searching problems ⋮ A meta-heuristic based goal-selection strategy for mobile robot search in an unknown environment ⋮ Online routing and searching on graphs with blocked edges ⋮ Exact and Approximation Algorithms for the Expanding Search Problem ⋮ A general framework for searching on a line ⋮ Competitive search in a network ⋮ Best-of-both-worlds analysis of online search ⋮ Multirobot search for a stationary object placed in a known environment with a combination of GRASP and VND ⋮ Algorithms for \(p\)-Faulty Search on a half-line ⋮ Online search with a hint ⋮ The \(k\)-server problem ⋮ Treasure evacuation with one robot on a disk ⋮ Multi-target ray searching problems ⋮ The expanding search ratio of a graph ⋮ Searching for multiple objects in multiple locations ⋮ Lower bounds in on-line geometric searching ⋮ Query strategies for priced information ⋮ The ultimate strategy to search on \(m\) rays? ⋮ Complexity of decision-theoretic troubleshooting ⋮ The Chinese deliveryman problem ⋮ Unnamed Item ⋮ Searching on a line: a complete characterization of the optimal solution ⋮ A new formulation for the traveling deliveryman problem ⋮ Weighted group search on a line \& implications to the priority evacuation problem ⋮ Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems ⋮ Graph exploration by energy-sharing mobile agents