{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T14:32:28Z","timestamp":1773325948789,"version":"3.50.1"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2011,7,1]],"date-time":"2011-07-01T00:00:00Z","timestamp":1309478400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2011,7]]},"abstract":"<jats:p>\n            In the\n            <jats:italic>mobile facility location<\/jats:italic>\n            problem, which is a variant of the classical facility location, each facility and client is assigned to a start location in a metric graph and our goal is to find a destination node for each client and facility such that every client is sent to a node which is the destination of some facility. The quality of a solution can be measured either by the total distance clients and facilities travel or by the maximum distance traveled by any client or facility. As we show in this article (by an approximation-preserving reduction), the problem of minimizing the total movement of facilities and clients generalizes the classical\n            <jats:italic>k<\/jats:italic>\n            -median problem. The class of movement problems was introduced by Demaine et al. [2007] where a simple 2-approximation was proposed for the minimum maximum movement mobile facility location problem while an approximation for the minimum total movement variant and hardness results for both were left as open problems. Our main result here is an 8-approximation algorithm for the minimum total movement mobile facility location problem. Our algorithm is obtained by rounding an LP relaxation in five phases. For the minimum maximum movement mobile facility location problem, we show that we cannot have a better than a 2-approximation for the problem, unless\n            <jats:italic>P<\/jats:italic>\n            =\n            <jats:italic>NP<\/jats:italic>\n            so the simple algorithm proposed by Demaine et al. [2007] is essentially best possible.\n          <\/jats:p>","DOI":"10.1145\/1978782.1978783","type":"journal-article","created":{"date-parts":[[2011,7,21]],"date-time":"2011-07-21T13:27:09Z","timestamp":1311254829000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Minimizing movement in mobile facility location problems"],"prefix":"10.1145","volume":"7","author":[{"given":"Zachary","family":"Friggstad","sequence":"first","affiliation":[{"name":"University of Alberta, Edmonton, Alberta, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad R.","family":"Salavatipour","sequence":"additional","affiliation":[{"name":"University of Alberta, Edmonton, Alberta, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,7,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00144-1"},{"key":"e_1_2_1_2_1","first-page":"128","article-title":"On min-max r-gatherings. 2008. To appear in Theoretical Computer Science. In Lecture Notes in Computer Science","volume":"4927","author":"Armon A.","year":"2008","unstructured":"Armon , A. 2008 . On min-max r-gatherings. 2008. To appear in Theoretical Computer Science. In Lecture Notes in Computer Science , Springer , vol. 4927 , 128 -- 141 . Armon, A. 2008. On min-max r-gatherings. 2008. To appear in Theoretical Computer Science. In Lecture Notes in Computer Science, Springer, vol. 4927, 128--141.","journal-title":"Springer"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702416402"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276725"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/345848.345858"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1062689.1062729"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74208-1_3"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301257"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703405754"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 258--267","author":"Demaine E.","unstructured":"Demaine , E. , Hajiaghayi , M. , Mahini , H. , Sayid-Roshkar , A. , Oveisgharan , S. , and Zadimoghaddam , M . 2007. Minimizing movement . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 258--267 . Demaine, E., Hajiaghayi, M., Mahini, H., Sayid-Roshkar, A., Oveisgharan, S., and Zadimoghaddam, M. 2007. Minimizing movement. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 258--267."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 649--657","author":"Guha S.","unstructured":"Guha , S. and Khuller , S . 1998. Greedy strikes back: Improved facility location algorithms . In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 649--657 . Guha, S. and Khuller, S. 1998. Greedy strikes back: Improved facility location algorithms. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 649--657."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581035"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 5th Workshop on Algorithmic Foundations of Robotics (WAFR). 77--94","author":"Hsiang T.-R.","unstructured":"Hsiang , T.-R. , Arkin , E. , Bender , M. , Fekete , S. , and Mitchell , J . 2002. Algorithms for rapidly dispersing robot swarms in unknown environments . In Proceedings of the 5th Workshop on Algorithmic Foundations of Robotics (WAFR). 77--94 . Hsiang, T.-R., Arkin, E., Bender, M., Fekete, S., and Mitchell, J. 2002. Algorithms for rapidly dispersing robot swarms in unknown environments. In Proceedings of the 5th Workshop on Algorithmic Foundations of Robotics (WAFR). 77--94."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/950620.950621"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510012"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375845"},{"key":"e_1_2_1_19_1","volume-title":"Complexity of Computer Computations","author":"Karp R.","unstructured":"Karp , R. 1972. Reducibility among combinatorial problems . In Complexity of Computer Computations , R. Miller and J. Thatcher Eds., Plenum Press , 85--103. Karp, R. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. Miller and J. Thatcher Eds., Plenum Press, 85--103."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_38"},{"key":"e_1_2_1_21_1","volume-title":"Combinatorial Optimization - Polyhedra and Efficiency","author":"Schrijver A.","unstructured":"Schrijver , A. 2003. Combinatorial Optimization - Polyhedra and Efficiency . Springer . Schrijver, A. 2003. Combinatorial Optimization - Polyhedra and Efficiency. Springer."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258600"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/645591.659950"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703435716"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 801--810","author":"Zhang J.","year":"2004","unstructured":"Zhang , J. 2004 . Approximating the two-level facility location problem via a quasi-greedy approach . In Proceedings of 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 801--810 . Zhang, J. 2004. Approximating the two-level facility location problem via a quasi-greedy approach. In Proceedings of 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 801--810."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.05.024"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1978782.1978783","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1978782.1978783","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:37Z","timestamp":1750244377000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1978782.1978783"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["10.1145\/1978782.1978783"],"URL":"https:\/\/doi.org\/10.1145\/1978782.1978783","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,7]]},"assertion":[{"value":"2008-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-07-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}