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

DOI10.1007/978-3-319-03578-9_27zbMATH Open1353.68254arXiv1407.0628OpenAlexW2202924637MaRDI QIDQ2868655FDOQ2868655

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

Publication date: 17 December 2013

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• On the hardness of approximating minimum vertex cover
• On Representatives of Subsets
• On the power of unique 2-prover 1-round games
• O(1)-Approximations for Maximum Movement Problems
• Minimizing Movement: Fixed-Parameter Tractability
• Minimizing movement in mobile facility location problems
• Title not available (Why is that?)

Cited In (4)

• Graphs, Maneuvers and Turnpikes
• Exact and approximate algorithms for movement problems on (special classes of) graphs
• Social network coordination and graph routing
• 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)