Approximation algorithms for the arc orienteering problem

In this article we present approximation algorithms for the Arc Orienteering Problem (AOP). We propose a polylogarithmic approximation algorithm in directed graphs, while in undirected graphs we give a (6+ϵ+o(1)) and a (4+ϵ)-approximation algorithm for arbitrary instances and instances of unit profit, respectively. Also, an inapproximability result for the AOP is obtained as well as approximation algorithms for the Mixed Orienteering Problem.