Approximation and complexity of multi-target graph search and the Canadian traveler problem
DOI10.1016/j.tcs.2018.04.022zbMath1395.68158OpenAlexW2802261039WikidataQ129967209 ScholiaQ129967209MaRDI QIDQ1637225
Publication date: 7 June 2018
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://ir.cwi.nl/pub/27650
computational complexityapproximation algorithmsgraph search problemCanadian traveler problemrouting under uncertainty
Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity of Canadian traveler problem variants
- Shortest paths without a map
- A note on the \(k\)-Canadian traveller problem
- An improved approximation ratio for the minimum latency problem
- Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
- Approximating min sum set cover
- A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
- The minimum latency problem
- Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width Four
- Saving an epsilon
- P-Complete Approximation Problems
- A General Approximation Technique for Constrained Forest Problems
- Stochastic shortest path problems with recourse
- Reducibility among Combinatorial Problems
- Polynomial time approximation schemes for the traveling repairman and other minimum latency problems.
This page was built for publication: Approximation and complexity of multi-target graph search and the Canadian traveler problem
