An Improved FPTAS for Mobile Agent Routing with Time Constraints

Camponogara and shima (2010) developed an ε-approximation algorithm (fptas) for the mobile agent routing problem in which a benefit function determines how visits to different sites contribute to the agent’s mission. the benefit is to be maximized under a time constraint. they reduced the problem to the constrained longest-path problem in a graph. in this note we present a modified fptas that improves on their result by a factor of (n/ h)loglog(b / b) , where b and b are an upper bound and a lower bound on the maximum benefit, respectively, n is the number of nodes, and h is the length of the longest path (in hops) in the graph.