An improved FPTAS for mobile agent routing with time constraints

Abstract

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 [refer to publisher pdf], where [refer to publisher pdf] 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.