An Improved FPTAS for Mobile Agent Routing with Time Constraints

Eugene Levner (Ashkelon Academic College and Bar Ilan University, Israel)

Amir Elalouf (Bar Ilan University, Israel)

T.C. Edwin Cheng (The Hong Kong Polytechnic University, Hong Kong)

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 , where and 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.

Keywords: FPTAS, approximation algorithm, constrained longest path, constrained routing, mobile agent

Categories: F.2.2, G.2.2, I.2.11, J.7