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

Corresponding author: Eugene Levner ( elevner@ash-college.ac.il )

© Eugene Levner, Amir Elalouf, T. C. Cheng.
This article is freely available under the J.UCS Open Content License.
Citation: Levner E, Elalouf A, Cheng TCE (2011) An Improved FPTAS for Mobile Agent Routing with Time Constraints. JUCS - Journal of Universal Computer Science 17(13): 1854-1862. https://doi.org/10.3217/jucs-017-13-1854
Open Access
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
mobile agent, constrained routing, constrained longest path, approximation algorithm, FPTAS