JUCS - Journal of Universal Computer Science 17(13): 1854-1862, doi: 10.3217/jucs-017-13-1854
An Improved FPTAS for Mobile Agent Routing with Time Constraints
expand article infoEugene Levner, Amir Elalouf§, T. C. Edwin Cheng|
‡ Ashkelon Academic College and Bar Ilan University, Ramat Gan, Israel§ Bar Ilan University, Ramat Gan, Israel| The Hong Kong Polytechnic University, Hong Kong, Hong Kong
Open Access
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.
mobile agent, constrained routing, constrained longest path, approximation algorithm, FPTAS