Paper by Erik D. Demaine
- Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dániel Marx, “Minimizing Movement: Fixed-Parameter Tractability”, in Proceedings of the 17th Annual European Symposium on Algorithms (ESA 2009), Lecture Notes in Computer Science, volume 5757, Copenhagen, Denmark, September 7–9, 2009, pages 718–729.
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.
- The full paper is available as arXiv.org:1205.6960 of the Computing Research Repository (CoRR).
- Copyright held by the authors.
- The paper is 12 pages.
- The paper is available in PostScript (313k), gzipped PostScript (139k), and PDF (180k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- MovementFPT_TALG (Minimizing Movement: Fixed-Parameter Tractability)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated November 16, 2017 by