Improved Algorithms for Orienteering and Related Problems
Improved Algorithms for Orienteering and Related Problems
复制标题
DOI：
10.1145/2229163.2229167
复制
发表时间：
2012-07-01
影响因子：
1.3
通讯作者：
Pal, Martin
中科院分区：
文献类型：
--
作者：
Chekuri, Chandra;Korula, Nitish;Pal, Martin
在这篇文章中，我们考虑定向问题的无向图和有向图，并获得改进的近似算法。点到点定向问题如下：给定一个边加权图G =（V，E）（有向或无向），两个节点s，t是V的一个元素和一个时间限制B，在G中找到一个总长度至多为B的s-t行走，该行走最大化所访问的不同节点的数量。该问题与TSP等旅游问题以及K-MST等网络设计问题密切相关。有时间窗的定向是更一般的问题，其中每个节点v都有一个指定的时间窗[R（v），D（v）]，只有当v在其时间窗内被访问时，节点v才被视为被步行访问过。针对定向运动问题和带时间窗定向运动问题，设计了新的改进算法。我们的主要结果如下：-无向图中定向运动的（2 + 1）近似，改进了Bansal等人的3-近似。有向图中定向运动的O（log（2）OPT）近似，其中OPT
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), two nodes s, t is an element of V and a time limit 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. Orienteering with time-windows is the more general problem in which each node v has a specified time-window [R(v), D(v)] and a node v is counted as visited by the walk only if v is visited during its time-window. We design new and improved algorithms for the orienteering problem and orienteering with time-windows. Our main results are the following:-A (2 + epsilon) approximation for orienteering in undirected graphs, improving upon the 3-approximation of Bansal et al. [2004].-An O(log(2) OPT) approximation for orienteering in directed graphs, where OPT