Minimizing movement: Fixed-parameter tractability
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, e...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer Berlin / Heidelberg
2011
|
| Online Access: | http://hdl.handle.net/1721.1/61962 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1826199496107753472 |
|---|---|
| author | Demaine, Erik D. Hajiaghayi, Mohammad Taghi Marx, Daniel |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Demaine, Erik D. Hajiaghayi, Mohammad Taghi Marx, Daniel |
| author_sort | Demaine, Erik D. |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T11:21:10Z |
| format | Article |
| id | mit-1721.1/61962 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:21:10Z |
| publishDate | 2011 |
| publisher | Springer Berlin / Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/619622022-09-27T18:55:13Z Minimizing movement: Fixed-parameter tractability Demaine, Erik D. Hajiaghayi, Mohammad Taghi Marx, Daniel Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Demaine, Erik D. 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. Hungarian Scientific Research Foundation (OTKA) (grant 67651) 2011-03-25T15:09:51Z 2011-03-25T15:09:51Z 2009-09 2009-09 Article http://purl.org/eprint/type/ConferencePaper 978-3-642-04127-3 http://hdl.handle.net/1721.1/61962 Demaine, Erik, MohammadTaghi Hajiaghayi, and Dániel Marx. “Minimizing Movement: Fixed-Parameter Tractability.” Algorithms - ESA 2009. Springer Berlin / Heidelberg, 2009. 718-729-729. https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.1007/978-3-642-04128-0_64 Algorithms - ESA 2009. Proceedings of the 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer Berlin / Heidelberg MIT web domain |
| spellingShingle | Demaine, Erik D. Hajiaghayi, Mohammad Taghi Marx, Daniel 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 | http://hdl.handle.net/1721.1/61962 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT demaineerikd minimizingmovementfixedparametertractability AT hajiaghayimohammadtaghi minimizingmovementfixedparametertractability AT marxdaniel minimizingmovementfixedparametertractability |