Erik D. Demaine
Mohammadtaghi Hajiaghayi
Amin S. Sayedi-Roshkhar
Abstract
We give approximation algorithms and inapproximability results for a class of movement problems. In general, these problems involve planning the coordinated motion of a large collection of objects (representing anything from a robot swarm or firefighter team to map labels or network messages) to achieve a global property of the network while minimizing the maximum or average movement. In particular, we consider the goals of achieving connectivity (undirected and directed), achieving connectivity between a given pair of vertices, achieving independence (a dispersion problem), and achieving a perfect matching (with applications to multicasting). This general family of movement problems encompasses an intriguing range of graph and geometric algorithms, with several real-world applications and a surprising range of approximability. In some cases, we obtain tight approximation and inapproximability results using direct techniques (without use of PCP), assuming just that P ≠ NP.
- Arkin, E. M., Bender, M. A., Fekete, S. P., Mitchell, J. S. B., and Skutella, M. 2002. The freeze-tag problem: How to wake up a swarm of robots. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. 568--577. Google Scholar
Digital Library
- Arkin, E. M., Bender, M. A., and Ge, D. 2003. Improved approximation algorithms for the freeze-tag problem. In Proceedings of the 15th Annual ACM Symposium on Parallel Algorithms and Architectures. 295--303. Google ScholarDigital Library
- Bredin, J. L., Demaine, E. D., Hajiaghayi, M., and Rus, D. 2005. Deploying sensor networks with guaranteed capacity and fault tolerance. In Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC'05). 309--319. Google ScholarDigital Library
- Charikar, M., Chekuri, C., Cheung, T.-Y., Dai, Z., Goel, A., Guha, S., and Li, M. 1999. Approximation algorithms for directed steiner problems. J. Algor. 33, 1, 73--91. Google ScholarDigital Library
- Cohen, J. 1998. Broadcasting, multi-casting and gossiping in trees under the all-port line model. In Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures. 164--171. Google ScholarDigital Library
- Cohen, J., Fraigniaud, P., König, J.-C., and Raspaud, A. 1998. Optimized broadcasting and multi-casting protocols in cut-through routed networks. IEEE Trans. Parallel Distrib. Syst. 9, 8, 788--802. Google ScholarDigital Library
- Corke, P., Hrabar, S., Peterson, R., Rus, D., Saripalli, S., and Sukhatme, G. 2004a. Autonomous deployment of a sensor network using an unmanned aerial vehicle. In Proceedings of the International Conference on Robotics and Automation.Google Scholar
- Corke, P., Hrabar, S., Peterson, R., Rus, D., Saripalli, S., and Sukhatme, G. 2004b. Deployment and connectivity repair of a sensor net with a flying robot. In Proceedings of the 9th International Symposium on Experimental Robotics.Google Scholar
- Doddi, S., Marathe, M. V., Mirzaian, A., Moret, B. M. E., and Zhu, B. 1997. Map labeling and its generalizations. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms. 148--157. Google ScholarDigital Library
- Ghodsi, M., Hajiaghayi, M., Mahdian, M., and Mirrokni, V. S. 2002. Length-constrained path-matchings in graphs. Netw. 39, 4, 210--215.Google ScholarCross Ref
- Guha, S., and Khuller, S. 1999. Improved methods for approximating node weighted steiner trees and connected dominating sets. Inf. Comput. 150, 1, 57--74. Google ScholarDigital Library
- Hsiang, T.-R., Arkin, E. M., Bender, M. A., Fekete, S. P., and Mitchell, J. S. B. 2003. Algorithms for rapidly dispersing robot swarms in unknown environments. In Algorithmic Foundations of Robotics V, J.-D. Boissonnat et al., Eds. Springer Tracts in Advanced Robotics, vol. 7. Springer-Verlag, 77--94.Google Scholar
- Hunt, III, H. B., Marathe, M. V., Radhakrishnan, V., Ravi, S. S., Rosenkrantz, D. J., and Stearns, R. E. 1998. NC-Approximation schemes for NP- and PSPACE-hard problems for geometric graphs. J. Algor. 26, 2, 238--274. Google ScholarDigital Library
- Jiang, M., Bereg, S., Qin, Z., and Zhu, B. 2004. New bounds on map labeling with circular labels. In Proceedings of the 15th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 3341, 606--617. Google ScholarDigital Library
- Jiang, M., Qian, J., Qin, Z., Zhu, B., and Cimikowski, R. 2003. A simple factor-3 approximation for labeling points with circles. Inf. Process. Lett. 87, 2, 101--105. Google ScholarDigital Library
- Klein, P. N., and Ravi, R. 1995. A nearly best-possible approximation algorithm for node-weighted Steiner trees. J. Algor. 19, 1, 104--115. Google ScholarDigital Library
- LaValle, S. M. 2006. Planning Algorithms. Cambridge University Press. http://msl.cs.uiuc.edu/planning/. Google ScholarDigital Library
- Reif, J. H., and Wang, H. 1995. Social potential fields: A distributed behavioral control for autonomous robots. In Proceedings of the Workshop on Algorithmic Foundations of Robotics. 331--345. Google ScholarDigital Library
- Schultz, A. C., Parker, L. E., and Schneider, F. E., Eds. 2003. Multi-Robot Systems: From Swarms to Intelligent Automata. Proceedings from the International Workshop on Multi-Robot Systems. Springer.Google Scholar
- Strijk, T., and Wolff, A. 2001. Labeling points with circles. Int. J. Comput. Geom. Appl. 11, 2, 181--195.Google ScholarCross Ref
- Sztainberg, M. O., Arkin, E. M., Bender, M. A., and Mitchell, J. S. B. 2004. Theoretical and experimental analysis of heuristics for the “freeze-tag” robot awakening problem. IEEE Trans. Robotics Autom. 20, 4, 691--701. Google ScholarDigital Library
- West, D. B. 2001. Introduction to Graph Theory, 2nd Ed. Prentice Hall, Upper Saddle River.Google Scholar
Index Terms
- Minimizing movement
Recommendations
Minimizing Movement: Fixed-Parameter Tractability
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 ...
The Complexity of Planar Counting Problems
We prove the #P-hardness of the counting problems associated with various satisfiability, graph, and combinatorial problems, when restricted to planar instances. These problems include 3Sat, 1-3Sat, 1-Ex3Sat, Minimum Vertex Cover, Minimum Dominating Set,...
Clustering with partial information
The Correlation Clustering problem, also known as the Cluster Editing problem, seeks to edit a given graph by adding and deleting edges to obtain a collection of vertex-disjoint cliques, such that the editing cost is minimized. The Edge Clique ...
Comments