Minimizing Movement: Fixed-Parameter Tractability
© 2014 ACM. We study an extensive class of movement minimization problems that 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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/134274 |
| _version_ | 1811079042453995520 |
|---|---|
| author | Demaine, Erik D Hajiaghayi, Mohammadtaghi Marx, Dániel |
| author_facet | Demaine, Erik D Hajiaghayi, Mohammadtaghi Marx, Dániel |
| author_sort | Demaine, Erik D |
| collection | MIT |
| description | © 2014 ACM. We study an extensive class of movement minimization problems that 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 are mainly negative:manymovement 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. |
| first_indexed | 2024-09-23T11:09:08Z |
| format | Article |
| id | mit-1721.1/134274 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:09:08Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1342742022-03-30T14:26:24Z Minimizing Movement: Fixed-Parameter Tractability Demaine, Erik D Hajiaghayi, Mohammadtaghi Marx, Dániel © 2014 ACM. We study an extensive class of movement minimization problems that 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 are mainly negative:manymovement 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. 2021-10-27T20:04:16Z 2021-10-27T20:04:16Z 2014 2019-06-18T12:48:11Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/134274 en 10.1145/2650247 ACM Transactions on Algorithms Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) MIT web domain |
| spellingShingle | Demaine, Erik D Hajiaghayi, Mohammadtaghi Marx, Dániel Minimizing Movement: Fixed-Parameter Tractability |
| title | Minimizing Movement: Fixed-Parameter Tractability |
| title_full | Minimizing Movement: Fixed-Parameter Tractability |
| title_fullStr | Minimizing Movement: Fixed-Parameter Tractability |
| title_full_unstemmed | Minimizing Movement: Fixed-Parameter Tractability |
| title_short | Minimizing Movement: Fixed-Parameter Tractability |
| title_sort | minimizing movement fixed parameter tractability |
| url | https://hdl.handle.net/1721.1/134274 |
| work_keys_str_mv | AT demaineerikd minimizingmovementfixedparametertractability AT hajiaghayimohammadtaghi minimizingmovementfixedparametertractability AT marxdaniel minimizingmovementfixedparametertractability |