Minimizing Movement: Fixed-Parameter Tractability
From MaRDI portal
Abstract: We study an extensive class of movement minimization problems which arise from many practical scenarios but so far have little theoretical study. In general, these problems involve planning the coordinated motion of a collection of agents (representing robots, people, map labels, network messages, etc.) to achieve a global property in the network while minimizing the maximum or average movement (expended energy). The only previous theoretical results about this class of problems are about approximation, and mainly negative: many movement problems of interest have polynomial inapproximability. Given that the number of mobile agents is typically much smaller than the complexity of the environment, we turn to fixed-parameter tractability. We characterize the boundary between tractable and intractable movement problems in a very general set up: it turns out the complexity of the problem fundamentally depends on the treewidth of the minimal configurations. Thus the complexity of a particular problem can be determined by answering a purely combinatorial question. Using our general tools, we determine the complexity of several concrete problems and fortunately show that many movement problems of interest can be solved efficiently.
Recommendations
Cited in
(15)- Relief aid provision to en route refugees: multi-period mobile facility location with mobile demand
- Mobile facility location: combinatorial filtering via weighted occupancy
- Exact and approximate algorithms for movement problems on (special classes of) graphs
- 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
- Confronting intractability via parameters
- On the parameterized complexity of finding separators with non-hereditary properties
- Minimizing movement: fixed-parameter tractability
- Network movement games
- The parameterized complexity of motion planning for snake-like robots
- The deep minimizing movement scheme
- The parameterized complexity of coordinated motion planning
- Combinatorial filter reduction: special cases, approximation, and fixed-parameter tractability
This page was built for publication: Minimizing Movement: Fixed-Parameter Tractability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3639284)
