Computer Science – Data Structures and Algorithms
Scientific paper
2012-02-25
Computer Science
Data Structures and Algorithms
17 pages, 5 figures
Scientific paper
In this paper we consider the problem of planning a path for a robot to monitor a known set of features of interest in an environment. We represent the environment as a vertex- and edge-weighted graph, where vertices represent features or regions of interest. The edge weights give travel times between regions, and the vertex weights give the importance of each region. If the robot repeatedly performs a closed walk on the graph, then we can define the latency of a vertex to be the maximum time between visits to that vertex, weighted by the importance (vertex weight) of that vertex. Our goal in this paper is to find the closed walk that minimizes the maximum weighted latency of any vertex. We show that there does not always exist an optimal walk of polynomial size. We then prove that for any graph there exist a constant approximation walk of size O(n^2), where n is the number of vertices. We provide two approximation algorithms; an O(log n)-approximation and an O(log \rho)-approximation, where \rho is the ratio between the maximum and minimum vertex weight. We provide simulation results which demonstrate that our algorithms can be applied to problems consisting of thousands of vertices.
Alamdari Soroush
Fata Elaheh
Smith Stephen L.
No associations
LandOfFree
Min-Max Latency Walks: Approximation Algorithms for Monitoring Vertex-Weighted Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Min-Max Latency Walks: Approximation Algorithms for Monitoring Vertex-Weighted Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Min-Max Latency Walks: Approximation Algorithms for Monitoring Vertex-Weighted Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-290792