Chandra Chekuri
ABSTRACT
In this paper we consider the orienteering problem in undirected and directed graphs and obtain improved approximation algorithms. The point to point-orienteering-problem is the following: Given an edge-weighted graph G = (V, E) (directed or undirected), two nodes s, t ∈ V and a budget B, find an s-t walk in G of total length at most B that maximizes the number of distinct nodes visited by the walk. This problem is closely related to tour problems such as TSP as well as network design problems such as k-MST. Our main results are the following.
• A 2 + ε approximation in undirected graphs, improving upon the 3-approximation from [6].
• An O(log2 OPT) approximation in directed graphs. Previously, only a quasi-polynomial time algorithm achieved a poly-logarithmic approximation [14] (a ratio of O (log OPT)).
The above results are based on, or lead to, improved algorithms for several other related problems.
Index Terms
- Improved algorithms for orienteering and related problems
Recommendations
Improved algorithms for orienteering and related problems
In this article, we consider the orienteering problem in undirected and directed graphs and obtain improved approximation algorithms. The point to point-orienteering problem is the following: Given an edge-weighted graph G=(V, E) (directed or undirected)...
Improved Approximation Algorithms for Minimum Cost Node-Connectivity Augmentation Problems
Let źG(s, t) denote the maximum number of pairwise internally disjoint st-paths in a graph G = (V, E). For a set T⊆V$T \subseteq V$ of terminals, G is k-T-connected if źG(s, t) ź k for all s, t ź T; if T = V then G is k-connected. Given a root node s, G ...
The Directed Orienteering Problem
This paper studies vehicle routing problems on asymmetric metrics. Our starting point is the directedk-TSP problem: given an asymmetric metric (V,d), a root rźV and a target k≤|V|, compute the minimum length tour that contains r and at least k other ...
Comments