{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:31:00Z","timestamp":1759638660939,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,10,30]],"date-time":"2014-10-30T00:00:00Z","timestamp":1414627200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"University of Maryland Research and Scholarship Award"},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-12-1-0423"],"award-info":[{"award-number":["FA9550-12-1-0423"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003549","name":"Orsz\u00e1gos Tudom\u00e1nyos Kutat\u00e1si Alapprogramok","doi-asserted-by":"publisher","award":["NK105645"],"award-info":[{"award-number":["NK105645"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1161626"],"award-info":[{"award-number":["CCF-1161626"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["FA9550-12-1-0423"],"award-info":[{"award-number":["FA9550-12-1-0423"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2014,11,17]]},"abstract":"<jats:p>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: 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.<\/jats:p>","DOI":"10.1145\/2650247","type":"journal-article","created":{"date-parts":[[2014,10,31]],"date-time":"2014-10-31T19:28:54Z","timestamp":1414783734000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Minimizing Movement: Fixed-Parameter Tractability"],"prefix":"10.1145","volume":"11","author":[{"given":"Erik D.","family":"Demaine","sequence":"first","affiliation":[{"name":"MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammadtaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, and AT&amp;T Labs--Research, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[{"name":"Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI) Budapest, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,10,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250801"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1062689.1062729"},{"volume-title":"The Complexity of Robot Motion Planning","author":"Canny J. F.","key":"e_1_2_1_4_1","unstructured":"J. F. Canny . 1987. The Complexity of Robot Motion Planning . MIT Press . J. F. Canny. 1987. The Complexity of Robot Motion Planning. MIT Press."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"P. Corke S. Hrabar R. Peterson D. Rus S. Saripalli and G. Sukhatme. 2004a. Autonomous deployment of a sensor network using an unmanned aerial vehicle. In ICRA.  P. Corke S. Hrabar R. Peterson D. Rus S. Saripalli and G. Sukhatme. 2004a. Autonomous deployment of a sensor network using an unmanned aerial vehicle. In ICRA.","DOI":"10.1109\/ROBOT.2004.1308811"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"volume-title":"Handbook of Theoretical Computer Science,Vol","author":"Courcelle B.","key":"e_1_2_1_7_1","unstructured":"B. Courcelle . 1990. Graph rewriting: An algebraic and logic approach . In Handbook of Theoretical Computer Science,Vol . B. Elsevier , Amsterdam , 193--242. B. Courcelle. 1990. Graph rewriting: An algebraic and logic approach. In Handbook of Theoretical Computer Science,Vol. B. Elsevier, Amsterdam, 193--242."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm033"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.14"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1541885.1541891"},{"key":"e_1_2_1_11_1","unstructured":"S. Doddi M. V. Marathe A. Mirzaian B. M. E. Moret and B. Zhu. 1997. Map labeling and its generalizations. In SODA. 148--157.   S. Doddi M. V. Marathe A. Mirzaian B. M. E. Moret and B. Zhu. 1997. Map labeling and its generalizations. In SODA. 148--157."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Springer New York.   R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Springer New York.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9239-2"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00014"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.03.021"},{"key":"e_1_2_1_16_1","unstructured":"J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag Berlin.   J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag Berlin."},{"key":"e_1_2_1_17_1","unstructured":"E. C. Freuder. 1990. Complexity of k-tree structured constraint satisfaction problems. In AAAI. 4--9.   E. C. Freuder. 1990. Complexity of k-tree structured constraint satisfaction problems. In AAAI. 4--9."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.12"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"volume-title":"Algorithms for rapidly dispersing robot swarms in unknown environments","author":"Hsiang T.-R.","key":"e_1_2_1_20_1","unstructured":"T.-R. Hsiang , E. M. Arkin , M. A. Bender , S. P. Fekete , and J. S. B. Mitchell . 2003. Algorithms for rapidly dispersing robot swarms in unknown environments . In Algorithmic Foundations of Robotics V. Springer, Berlin, Tracts in Advanced Robotics, Vol. 7 . Springer-Verlag , Berlin, 77--94. T.-R. Hsiang, E. M. Arkin, M. A. Bender, S. P. Fekete, and J. S. B. Mitchell. 2003. Algorithms for rapidly dispersing robot swarms in unknown environments. In Algorithmic Foundations of Robotics V. Springer, Berlin, Tracts in Advanced Robotics, Vol. 7. Springer-Verlag, Berlin, 77--94."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233481.1233493"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30551-4_53"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00256-4"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00414-5"},{"volume-title":"Lecture Notes in Computer Science","author":"Kloks T.","key":"e_1_2_1_25_1","unstructured":"T. Kloks . 1994. Treewidth. Lecture Notes in Computer Science , Vol. 842 . Springer-Verlag , Berlin . T. Kloks. 1994. Treewidth. Lecture Notes in Computer Science, Vol. 842. Springer-Verlag, Berlin."},{"volume-title":"Planning Algorithms","author":"LaValle S. M.","key":"e_1_2_1_26_1","unstructured":"S. M. LaValle . 2006. Planning Algorithms . Cambridge University Press . http:\/\/msl.cs.uiuc.edu\/planning\/. S. M. LaValle. 2006. Planning Algorithms. Cambridge University Press. http:\/\/msl.cs.uiuc.edu\/planning\/."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11440-3_25"},{"key":"e_1_2_1_28_1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Plehn J.","year":"1990","unstructured":"J. Plehn and B. Voigt . 1991. Finding minimally weighted subgraphs . In Graph-Theoretic Concepts in Computer Science ( Berlin , 1990 ). Lecture Notes in Computer Science, vol. 484. Springer, Berlin, 18--29. J. Plehn and B. Voigt. 1991. Finding minimally weighted subgraphs. In Graph-Theoretic Concepts in Computer Science (Berlin, 1990). Lecture Notes in Computer Science, vol. 484. Springer, Berlin, 18--29."},{"volume-title":"Proceedings of the Workshop on Algorithmic Foundations of Robotics. 331--345","author":"Reif J. H.","key":"e_1_2_1_29_1","unstructured":"J. H. Reif and H. Wang . 1995. Social potential fields: A distributed behavioral control for autonomous robots . In Proceedings of the Workshop on Algorithmic Foundations of Robotics. 331--345 . J. H. Reif and H. Wang. 1995. Social potential fields: A distributed behavioral control for autonomous robots. In Proceedings of the Workshop on Algorithmic Foundations of Robotics. 331--345."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1073"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings from the 2003 International Workshop on Multi-Robot Systems. Springer","author":"Schultz A. C.","year":"2003","unstructured":"A. C. Schultz , L. E. Parker , and F. E. Schneider ( Eds .). 2003 . Multi-robot systems: From swarms to intelligent automata . In Proceedings from the 2003 International Workshop on Multi-Robot Systems. Springer , Berlin. A. C. Schultz, L. E. Parker, and F. E. Schneider (Eds.). 2003. Multi-robot systems: From swarms to intelligent automata. In Proceedings from the 2003 International Workshop on Multi-Robot Systems. Springer, Berlin."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195901000444"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2650247","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2650247","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:11:54Z","timestamp":1750227114000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2650247"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,30]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,11,17]]}},"alternative-id":["10.1145\/2650247"],"URL":"https:\/\/doi.org\/10.1145\/2650247","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2014,10,30]]},"assertion":[{"value":"2012-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}