{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T15:25:45Z","timestamp":1778081145218,"version":"3.51.4"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,4,13]],"date-time":"2023-04-13T00:00:00Z","timestamp":1681344000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61972309, 62272369, and 61976168"],"award-info":[{"award-number":["61972309, 62272369, and 61976168"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"CCF-Huawei Database System Innovation Research Plan","award":["2020010B"],"award-info":[{"award-number":["2020010B"]}]},{"name":"Key Scientific Research Program of Shaanxi Provincial Department of Education","award":["20JY014"],"award-info":[{"award-number":["20JY014"]}]},{"name":"Natural Science Basic Research Program of Shaanxi","award":["2023-JC-YB-558"],"award-info":[{"award-number":["2023-JC-YB-558"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>\n            Facility Relocation (FR), which is an effort to reallocate the placement of facilities to adapt to the changes of urban planning, has remarkable impact on many areas. Existing solutions fail to guarantee the result quality on relocating\n            <jats:italic>k &gt; 1<\/jats:italic>\n            facilities. As\n            <jats:italic>k<\/jats:italic>\n            -FR problem is NP-complete and is not submodular or non-decreasing, traditional greedy algorithm cannot be directly applied. We propose to transform\n            <jats:italic>k<\/jats:italic>\n            -FR into another facility placement problem, which is submodular and non-decreasing. We prove that the optimal solutions of both problems are equivalent. Accordingly, we present the first approximate solution toward the\n            <jats:italic>k<\/jats:italic>\n            -FR, FR2FP. Our extensive comparison over both FR2FP and the state-of-the-art solution shows that FR2FP, although it provides approximation guarantee, cannot necessarily given superior results. The comparison motivates us to present an advanced approximate solution, FR2FP-ex. Moreover, based on Lagrangian relaxation, we develop an algorithm that can adjust the approximation ratio. Extensive experiments verified that, FR2FP-ex demonstrates the best result quality, and it is very close to the optimal solution. In addition, we also unveil the scenarios when the state-of-the-art would fail. We further generalize the\n            <jats:italic>k<\/jats:italic>\n            -FR problem, considering the budget for relocation and the cost of each facility. We also present corresponding approximate solutions toward the new problem and prove the approximation ratio.\n          <\/jats:p>","DOI":"10.1145\/3587039","type":"journal-article","created":{"date-parts":[[2023,3,9]],"date-time":"2023-03-09T10:56:58Z","timestamp":1678359418000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Toward Balancing the Efficiency and Effectiveness in k-Facility Relocation Problem"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1373-3951","authenticated-orcid":false,"given":"Hu","family":"Wang","sequence":"first","affiliation":[{"name":"Xidian University, Xi\u2019an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2382-6289","authenticated-orcid":false,"given":"Hui","family":"Li","sequence":"additional","affiliation":[{"name":"Xidian University, Xi\u2019an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6699-6902","authenticated-orcid":false,"given":"Meng","family":"Wang","sequence":"additional","affiliation":[{"name":"Xi\u2019an Polytechnic University, Xi\u2019an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5569-0780","authenticated-orcid":false,"given":"Jiangtao","family":"Cui","sequence":"additional","affiliation":[{"name":"Xidian University, Xi\u2019an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,4,13]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1145\/2588555.2612172","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Chen Zitong","year":"2014","unstructured":"Zitong Chen, Yubao Liu, Raymond Chi-Wing Wong, Jiamin Xiong, Ganglin Mai, and Cheng Long. 2014. Efficient algorithms for optimal location queries in road networks. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 123\u2013134."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.23.8.789"},{"key":"e_1_3_2_4_2","volume-title":"The Uncapicitated Facility Location Problem","author":"Cornu\u00e9jols G\u00e9rard","year":"1983","unstructured":"G\u00e9rard Cornu\u00e9jols, George Nemhauser, and Laurence Wolsey. 1983. The Uncapicitated Facility Location Problem. Technical Report. Cornell University Operations Research and Industrial Engineering."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2018.06.036"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121195"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806508"},{"key":"e_1_3_2_8_2","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/978-3-540-68279-0_9","volume-title":"50 Years of Integer Programming 1958\u20132008: From the Early Years to the State-of-the-Art","author":"Geoffrion Arthur M.","year":"2010","unstructured":"Arthur M. Geoffrion. 2010. Lagrangian relaxation for integer programming. In 50 Years of Integer Programming 1958\u20132008: From the Early Years to the State-of-the-Art. Springer, 243\u2013281."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/1869790.1869866"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2014.09.004"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536459"},{"key":"e_1_3_2_13_2","first-page":"273","volume-title":"Proceedings of the International Symposium on Spatial and Temporal Databases","author":"Li Feifei","year":"2005","unstructured":"Feifei Li, Dihan Cheng, Marios Hadjieleftheriou, George Kollios, and Shang-Hua Teng. 2005. On trip planning queries in spatial databases. In Proceedings of the International Symposium on Spatial and Temporal Databases. Springer, 273\u2013290."},{"key":"e_1_3_2_14_2","first-page":"1","volume-title":"Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems","author":"Li Yuhong","year":"2015","unstructured":"Yuhong Li, Yu Zheng, Shenggong Ji, Wenjun Wang, Leong Hou U, and Zhiguo Gong. 2015. Location selection for ambulance stations: A data-driven approach. In Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. 1\u20134."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835942"},{"issue":"1","key":"e_1_3_2_16_2","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.ejor.2013.02.033","article-title":"\\(\\gamma\\) -robust facility relocation problem","volume":"229","author":"Lim Gino J.","year":"2013","unstructured":"Gino J. Lim and Ayse Durukan Sonmez. 2013. \\(\\gamma\\) -robust facility relocation problem. Eur. J. Oper. Res. 229, 1 (2013), 67\u201374.","journal-title":"Eur. J. Oper. Res."},{"key":"e_1_3_2_17_2","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/11535331_4","volume-title":"Proceedings of the International Symposium on Spatial and Temporal Databases","author":"Mouratidis Kyriakos","year":"2005","unstructured":"Kyriakos Mouratidis, Dimitris Papadias, and Spiros Papadimitriou. 2005. Medoid queries in large spatial databases. In Proceedings of the International Symposium on Spatial and Temporal Databases. Springer, 55\u201372."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.25.4.709"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.3.3.177"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071616"},{"key":"e_1_3_2_22_2","first-page":"366","volume-title":"Proceedings of the IEEE 28th International Conference on Data Engineering","author":"Qi Jianzhong","year":"2012","unstructured":"Jianzhong Qi, Rui Zhang, Lars Kulik, Dan Lin, and Yuan Xue. 2012. The min-dist location selection query. In Proceedings of the IEEE 28th International Conference on Data Engineering. IEEE, 366\u2013377."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-013-0223-7"},{"issue":"2","key":"e_1_3_2_24_2","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/j.ejor.2011.10.028","article-title":"A decomposition approach for facility location and relocation problem with uncertain number of future facilities","volume":"218","author":"Sonmez Ayse Durukan","year":"2012","unstructured":"Ayse Durukan Sonmez and Gino J. Lim. 2012. A decomposition approach for facility location and relocation problem with uncertain number of future facilities. Eur. J. Oper. Res. 218, 2 (2012), 327\u2013338.","journal-title":"Eur. J. Oper. Res."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374389"},{"key":"e_1_3_2_26_2","first-page":"2371","volume-title":"Proceedings of the 25th ACM International Conference on Information and Knowledge Management (CIKM\u201916)","author":"Wang Feng","year":"2016","unstructured":"Feng Wang, Li Chen, and Weike Pan. 2016. Where to place your next restaurant?: Optimal restaurant placement via leveraging user-generated reviews. In Proceedings of the 25th ACM International Conference on Information and Knowledge Management (CIKM\u201916). ACM, 2371\u20132376."},{"key":"e_1_3_2_27_2","first-page":"1919","volume-title":"Proceedings of the 30th ACM International Conference on Information and Knowledge Management (CIKM\u201921)","author":"Wang Hu","year":"2021","unstructured":"Hu Wang, Hui Li, Meng Wang, and Jiangtao Cui. 2021. Addressing the hardness of k-facility relocation problem: A pair of approximate solutions. In Proceedings of the 30th ACM International Conference on Information and Knowledge Management (CIKM\u201921). ACM, 1919\u20131928."},{"issue":"1","key":"e_1_3_2_28_2","first-page":"9","article-title":"FROST: Movement history-conscious facility relocation","volume":"11","author":"Wang Meng","year":"2020","unstructured":"Meng Wang, Hui Li, Jiangtao Cui, Sourav S. Bhowmick, and Ping Liu. 2020. FROST: Movement history-conscious facility relocation. ACM Trans. Intell. Syst. Technol. 11, 1, Article 9 (Jan.2020), 26 pages.","journal-title":"ACM Trans. Intell. Syst. Technol."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2580138"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(02)00123-5"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1080\/03155986.1983.11731889"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.2307\/1938423"},{"key":"e_1_3_2_33_2","first-page":"804","volume-title":"Proceedings of the IEEE 27th International Conference on Data Engineering","author":"Xiao Xiaokui","year":"2011","unstructured":"Xiaokui Xiao, Bin Yao, and Feifei Li. 2011. Optimal location queries in road network databases. In Proceedings of the IEEE 27th International Conference on Data Engineering. IEEE, 804\u2013815."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402734"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2009916.2009962"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.87"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164183"},{"key":"e_1_3_2_38_2","doi-asserted-by":"crossref","first-page":"2423","DOI":"10.1145\/3132847.3133067","volume-title":"Proceedings of the ACM on Conference on Information and Knowledge Management (CIKM\u201917)","author":"Zhang Yu","year":"2017","unstructured":"Yu Zhang, Wei Wei, Binxuan Huang, Kathleen M. Carley, and Yan Zhang. 2017. RATE: Overcoming noise and sparsity of textual features in real-time location estimation. In Proceedings of the ACM on Conference on Information and Knowledge Management (CIKM\u201917). ACM, 2423\u20132426."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526816"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/1869790.1869876"}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3587039","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3587039","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:33Z","timestamp":1750178253000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3587039"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,13]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1145\/3587039"],"URL":"https:\/\/doi.org\/10.1145\/3587039","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"value":"2157-6904","type":"print"},{"value":"2157-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,13]]},"assertion":[{"value":"2022-08-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-15","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}