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

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

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

• O(1)-approximations for maximum movement problems
• 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
• Minimizing movement in mobile facility location problems
• Minimizing Movement: Fixed-Parameter Tractability
• 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 \)

Cited in

(14)

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

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)