Approximation Algorithms for Stochastic k-TSP

2016/10/04 by Alina Ene, Ene, Alina, Viswanath Nagarajan +3 · 1 citation
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Scheduling and Optimization Algorithms #Vehicle Routing Optimization Methods

paper · pdf · doi:10.48550/arxiv.1610.01058

openalex publication_date 2016/10/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the stochastic k-TSP problem where rewards at vertices are random and the objective is to minimize the expected length of a tour that collects reward k. We present an adaptive O(log k)-approximation algorithm, and a non-adaptive O(log²k)-approximation algorithm. We also show that the adaptivity gap of this problem is between e and O(log²k).

Cited by

• Non-Adaptive Evaluation of k-of-n Functions: Tight Gap and a Unit-Cost PTAS

Related

• Algorithms and Adaptivity Gaps for Stochastic k-TSP
• Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap
• Approximation Algorithms for P2P Orienteering and Stochastic Vehicle\n Routing Problem
• On the Adaptivity Gap of Stochastic Orienteering
• Scalefree hardness of average-case Euclidean TSP approximation