Loading...
Please wait, while we are loading the content...
Similar Documents
Minimizing Movement: Fixed-Parameter Tractability (2012)
| Content Provider | CiteSeerX |
|---|---|
| Author | Demaine, Erik D. Hajiaghayi, Mohammadtaghi Marx, Dániel |
| 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 coordi-nated 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 setup: 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. |
| File Format | |
| Publisher Date | 2012-01-01 |
| Access Restriction | Open |
| Content Type | Text |
