An improved FPTAS for mobile agent routing with time constraints

Eugene Levner, Amir Elalouf, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

13 Citations (Scopus)

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 (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.
Original languageEnglish
Pages (from-to)1854-1862
Number of pages9
JournalJournal of Universal Computer Science
Volume17
Issue number13
Publication statusPublished - 20 Dec 2011

Keywords

  • Approximation algorithm
  • Constrained longest path
  • Constrained routing
  • FPTAS
  • Mobile agent

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this