Approximation Algorithms for Arc Orienteering Problems

In this paper we study the Arc Orienteering Problem in directed and undirected graphs. To the best of our knowledge, we give the st approximation algorithms for both the undirected and the directed versions of the problem. Our main results are the following: (i) We give an O( log2(m) / log log(m))-approximation algorithm for the AOP in directed graphs, where m is the number of arcs of the graph of the problem, using the O( log^2(n) / log log(n))-approximation for the OP in directed graphs found in [13]. (ii) Using the (2+ε)-approximation algorithm for the unweighted version of the OP in [6], we obtain a (6+ε+o(1))-approximation algorithm for the AOP in undirected graphs and a (4+ε)-approximation algorithm for the unweighted version of the AOP in undirected graphs. Moreover, we prove that the Mixed Orienteering Problem (MOP) can be reduced to AOP and that any approximation algorithm for the AOP yields an approximation algorithm for the MOP.