Approximation Algorithms for Orienteering and Discounted-Reward TSP

DOI10.1137/050645464zbMath1137.90687MaRDI QIDQ5386217

Terran Lane, Maria Minkoff, Adam Meyerson, Shuchi Chawla, David R. Karger, Avrim L. Blum

Publication date: 22 April 2008

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/a38aa3aedc1ba1a4f240b598ef5b1e9fdf08da29

zbMATH Keywords

Markov decision processes traveling salesman problem approximation algorithms robot navigation orienteering prize-collecting traveling salesman problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Related Items (42)

A constant-factor approximation for directed latency in quasi-polynomial time ⋮ Faster algorithms for orienteering and $k$-TSP ⋮ Approximation algorithms for distance constrained vehicle routing problems ⋮ An adaptive large neighborhood search for relocating vehicles in electric carsharing services ⋮ UAV routing for reconnaissance mission: a multi-objective orienteering problem with time-dependent prizes and multiple connections ⋮ On Maximum Discounted Effort Reward Search Problem ⋮ Approximation algorithms for the directed $k$-Tour and $k$-Stroll problems ⋮ Combinatorial algorithms for rooted prize-collecting walks and applications to orienteering and minimum-latency problems ⋮ Two multi-start heuristics for the $k$-traveling salesman problem ⋮ The school bus problem on trees ⋮ Orienteering for electioneering ⋮ On the adaptivity gap of stochastic orienteering ⋮ Delivery route optimization with automated vehicle in smart urban environment ⋮ Hybridized evolutionary local search algorithm for the team orienteering problem with time windows ⋮ Beating the Integrality Ratio for $s$-$t$-Tours in Graphs ⋮ Pruning 2-connected graphs ⋮ Approximation algorithms for the traveling repairman and speeding deliveryman problems ⋮ Dynamic Traveling Repair Problem with an Arbitrary Time Window ⋮ Discounted reward TSP ⋮ Complexity and approximation for traveling salesman problems with profits ⋮ The Directed Minimum Latency Problem ⋮ Approximation algorithms for the arc orienteering problem ⋮ A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time ⋮ The capacitated orienteering problem ⋮ Tour recommendation for groups ⋮ Capacitated Vehicle Routing with Non-uniform Speeds ⋮ Heuristic algorithms for the operator-based relocation problem in one-way electric carsharing systems ⋮ Grasp and delivery for moving objects on broken lines ⋮ The directed orienteering problem ⋮ The Robot Routing Problem for Collecting Aggregate Stochastic Rewards ⋮ Capacitated Vehicle Routing with Nonuniform Speeds ⋮ Improving the approximation ratio for capacitated vehicle routing ⋮ New approximation algorithms for the rooted budgeted cycle cover problem ⋮ Improving the approximation ratio for capacitated vehicle routing ⋮ New approximation algorithms for the rooted budgeted cycle cover problem ⋮ Exploring and Triangulating a Region by a Swarm of Robots ⋮ Stochastic graph exploration ⋮ Unnamed Item ⋮ Running Errands in Time: Approximation Algorithms for Stochastic Orienteering ⋮ Reducing Path TSP to TSP ⋮ Unnamed Item ⋮ Serving rides of equal importance for time-limited dial-a-ride

This page was built for publication: Approximation Algorithms for Orienteering and Discounted-Reward TSP