Exact and approximate algorithms for movement problems on (special classes of) graphs

DOI10.1007/978-3-319-03578-9_27MaRDI QIDQ2868655zbMATH OpenOpenAlexFDO

Authors D. Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti

Publication date 17 December 2013

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.0628

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Nonnumerical algorithms (68W05) Approximation algorithms (68W25)

Abstract: When a large collection of objects (e.g., robots, sensors, etc.) has to be deployed in a given environment, it is often required to plan a coordinated motion of the objects from their initial position to a final configuration enjoying some global property. In such a scenario, the problem of minimizing some function of the distance travelled, and therefore energy consumption, is of vital importance. In this paper we study several motion planning problems that arise when the objects must be moved on a graph, in order to reach certain goals which are of interest for several network applications. Among the others, these goals include broadcasting messages and forming connected or interference-free networks. We study these problems with the aim of minimizing a number of natural measures such as the average/overall distance travelled, the maximum distance travelled, or the number of objects that need to be moved. To this respect, we provide several approximability and inapproximability results, most of which are tight.

Recommendations

• Exact and approximate algorithms for movement problems on (special classes of) graphs
• Minimizing movement
• Minimizing movement
• \(O(1)\)-approximations for maximum movement problems
• Euclidean movement minimization

Cites work

• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• Minimizing Movement: Fixed-Parameter Tractability
• Minimizing movement
• Minimizing movement in mobile facility location problems
• On Representatives of Subsets
• On the hardness of approximating minimum vertex cover
• On the power of unique 2-prover 1-round games
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• \(O(1)\)-approximations for maximum movement problems

Cited in

(14)

• Minimizing Movement: Fixed-Parameter Tractability
• Minimizing movement
• Graphs, Maneuvers and Turnpikes
• Efficient motion planning strategies for large-scale sensor networks
• Euclidean movement minimization
• Optimizing movement in convex and non-convex path-networks to establish connectivity
• Exact and approximate algorithms for movement problems on (special classes of) graphs
• \(O(1)\)-approximations for maximum movement problems
• Social network coordination and graph routing
• Minimizing movement: fixed-parameter tractability
• Polygon-constrained motion planning problems
• On the fastest moving off from a vertex in directed regular graphs
• Optimizing movement in convex and non-convex path-networks to establish connectivity
• Minimizing movement

This page was built for publication: Exact and approximate algorithms for movement problems on (special classes of) graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2868655)