{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:07:11Z","timestamp":1750306031872,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,4,16]],"date-time":"2018-04-16T00:00:00Z","timestamp":1523836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001804","name":"Canada Research Chairs award","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001804","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Ontario Early Researcher Award"},{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","award":["327620-09"],"award-info":[{"award-number":["327620-09"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSERC Discovery Accelerator Supplement Award"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,4,30]]},"abstract":"\n We consider a facility-location problem that abstracts settings where the cost of serving the clients assigned to a facility is incurred by the facility. Formally, we consider the\n minimum-load k-facility location<\/jats:italic>\n (ML\n k<\/jats:italic>\n FL) problem, which is defined as follows. We have a set\n F<\/jats:italic>\n of facilities, a set\n C<\/jats:italic>\n of clients, and an integer\n k<\/jats:italic>\n \u2265 0. Assigning client\n j<\/jats:italic>\n to a facility\n f<\/jats:italic>\n incurs a connection cost\n d<\/jats:italic>\n (\n f<\/jats:italic>\n ,\n j<\/jats:italic>\n ). The goal is to open a set\n F<\/jats:italic>\n \u2286\n F<\/jats:italic>\n of\n k<\/jats:italic>\n facilities and assign each client\n j<\/jats:italic>\n to a facility\n f<\/jats:italic>\n (\n j<\/jats:italic>\n )\u2208\n F<\/jats:italic>\n so as to minimize max\n \n f<\/jats:italic>\n \u2208\n <\/jats:sub>\n F<\/jats:italic>\n \u2211\n \n j<\/jats:italic>\n \u2208\n C<\/jats:italic>\n :\n f<\/jats:italic>\n (\n j<\/jats:italic>\n )=\n f<\/jats:italic>\n <\/jats:sub>\n d<\/jats:italic>\n (\n f<\/jats:italic>\n ,\n j<\/jats:italic>\n ); we call \u2211\n \n j<\/jats:italic>\n \u2208\n C<\/jats:italic>\n :\n f<\/jats:italic>\n (\n j<\/jats:italic>\n )=\n f<\/jats:italic>\n <\/jats:sub>\n d<\/jats:italic>\n (\n f<\/jats:italic>\n ,\n j<\/jats:italic>\n ) the\n load<\/jats:italic>\n of facility\n f<\/jats:italic>\n . This problem was studied under the name of min-max star cover in References\u00a0[3, 7], who (among other results) gave bicriteria approximation algorithms for ML\n k<\/jats:italic>\n FL for when\n F<\/jats:italic>\n =\n C<\/jats:italic>\n . ML\n k<\/jats:italic>\n FL is rather poorly understood, and only an\n O<\/jats:italic>\n (\n k<\/jats:italic>\n )-approximation is currently known for ML\n k<\/jats:italic>\n FL,\n even for line metrics<\/jats:italic>\n .\n <\/jats:p>\n \n Our main result is the\n first polytime approximation scheme<\/jats:italic>\n (PTAS) for ML\n k<\/jats:italic>\n FL on line metrics (note that no non-trivial true approximation of any kind was known for this metric). Complementing this, we prove that ML\n k<\/jats:italic>\n FL is strongly\n NP<\/jats:italic>\n -hard on line metrics. We also devise a quasi-PTAS for ML\n k<\/jats:italic>\n FL on tree metrics. ML\n k<\/jats:italic>\n FL turns out to be surprisingly challenging even on line metrics and resilient to attack by a variety of techniques that have been successfully applied to facility-location problems. For instance, we show that (a) even a configuration-style LP-relaxation has a bad integrality gap and (b) a multi-swap\n k<\/jats:italic>\n -median style local-search heuristic has a bad locality gap. Thus, we need to devise various novel techniques to attack ML\n k<\/jats:italic>\n FL.\n <\/jats:p>\n Our PTAS for line metrics consists of two main ingredients. First, we prove that there always exists a near-optimal solution possessing some nice structural properties. A novel aspect of this proof is that we first move to a mixed-integer LP (MILP) encoding of the problem and argue that a MILP-solution minimizing a certain potential function possesses the desired structure and then use a rounding algorithm for the generalized-assignment problem to \u201ctransfer\u201d this structure to the rounded integer solution. Complementing this, we show that these structural properties enable one to find such a structured solution via dynamic programming.<\/jats:p>","DOI":"10.1145\/3173047","type":"journal-article","created":{"date-parts":[[2018,4,18]],"date-time":"2018-04-18T17:21:50Z","timestamp":1524072110000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximation Algorithms for Minimum-Load\n k<\/i>\n -Facility Location"],"prefix":"10.1145","volume":"14","author":[{"given":"Sara","family":"Ahmadian","sequence":"first","affiliation":[{"name":"Department of Combinatorics and Optimization, University of Waterloo, Canada"}]},{"given":"Babak","family":"Behsaz","sequence":"additional","affiliation":[{"name":"Department of Computing Science, University of Alberta, Canada"}]},{"given":"Zachary","family":"Friggstad","sequence":"additional","affiliation":[{"name":"Department of Computing Science, University of Alberta, Canada"}]},{"given":"Amin","family":"Jorati","sequence":"additional","affiliation":[{"name":"Department of Computing Science, University of Alberta, Canada"}]},{"given":"Mohammad R.","family":"Salavatipour","sequence":"additional","affiliation":[{"name":"Department of Computing Science, University of Alberta, Canada"}]},{"given":"Chaitanya","family":"Swamy","sequence":"additional","affiliation":[{"name":"Department of Combinatorics and Optimization, University of Waterloo, Canada"}]}],"member":"320","published-online":{"date-parts":[[2018,4,16]]},"reference":[{"volume-title":"Proceedings of APPROX. 17--33","author":"Ahmadian S.","key":"e_1_2_1_1_1","unstructured":"S. Ahmadian , B. Behsaz , Z. Friggstad , A. Jorati , M. Salavatipour , and C. Swamy . 2014. Approximation algorithms for minimum-load -facility location . In Proceedings of APPROX. 17--33 . S. Ahmadian, B. Behsaz, Z. Friggstad, A. Jorati, M. Salavatipour, and C. Swamy. 2014. Approximation algorithms for minimum-load -facility location. In Proceedings of APPROX. 17--33."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07557-0_5"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1139720.1712364"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702416402"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1882"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.63"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"G. Even N. Garg J. K\u00f6nemann R. Ravi and A. Sinha. 2003. Covering graphs using trees and stars. Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (2003) 24--35. G. Even N. Garg J. K\u00f6nemann R. Ravi and A. Sinha. 2003. Covering graphs using trees and stars. Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (2003) 24--35.","DOI":"10.1007\/978-3-540-45198-3_3"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0207017"},{"key":"e_1_2_1_9_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 8 Co., New York, NY, USA. Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 8 Co., New York, NY, USA."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217033"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/950620.950621"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375845"},{"volume-title":"Approximation Algorithms for Min-max Vehicle Routing Problems. Master\u2019s thesis","author":"Jorati Amin","key":"e_1_2_1_13_1","unstructured":"Amin Jorati . 2013. Approximation Algorithms for Min-max Vehicle Routing Problems. Master\u2019s thesis . University of Alberta , Department of Computing Science. Amin Jorati. 2013. Approximation Algorithms for Min-max Vehicle Routing Problems. Master\u2019s thesis. University of Alberta, Department of Computing Science."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9740-5"},{"key":"e_1_2_1_15_1","volume-title":"Noordhoff","author":"Khintchine A.","year":"1956","unstructured":"A. Khintchine . 1956 . Kettenbr\u00fcche. Teubner, Leipzig. English translation: Continued Fractions , Noordhoff , Groningen , 1963. A. Khintchine. 1956. Kettenbr\u00fcche. Teubner, Leipzig. English translation: Continued Fractions, Noordhoff, Groningen, 1963."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/130938645"},{"key":"e_1_2_1_17_1","unstructured":"P. Mirchandani and R. Francis (Eds.). 1990. Discrete Location Theory. John Wiley 8 Sons. P. Mirchandani and R. Francis (Eds.). 1990. Discrete Location Theory. John Wiley 8 Sons."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.06.012"},{"key":"e_1_2_1_19_1","volume-title":"Workshop on Flexible Network Design.","author":"Ravi R.","year":"2012","unstructured":"R. Ravi . 2012 . Workshop on Flexible Network Design. Retrieved from http:\/\/fnd2012.mimuw.edu.pl\/qa\/index.php?qa=4&qa_1===approximating-star-cover-problems. R. Ravi. 2012. Workshop on Flexible Network Design. Retrieved from http:\/\/fnd2012.mimuw.edu.pl\/qa\/index.php?qa=4&qa_1===approximating-star-cover-problems."},{"key":"e_1_2_1_20_1","volume-title":"AMS Proceedings of Symposia in Applied Mathematics 61","author":"Shmoys D.","year":"2004","unstructured":"D. Shmoys . 2004 . The design and analysis of approximation algorithms: Facility location as a case study. In Trends in Optimization , AMS Proceedings of Symposia in Applied Mathematics 61 , S. Hosten, J. Lee, and R. Thomas (Eds.). 85--97. D. Shmoys. 2004. The design and analysis of approximation algorithms: Facility location as a case study. In Trends in Optimization, AMS Proceedings of Symposia in Applied Mathematics 61, S. Hosten, J. Lee, and R. Thomas (Eds.). 85--97."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/3113606.3113856"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3173047","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3173047","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:02:50Z","timestamp":1750215770000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3173047"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,16]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4,30]]}},"alternative-id":["10.1145\/3173047"],"URL":"https:\/\/doi.org\/10.1145\/3173047","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2018,4,16]]},"assertion":[{"value":"2016-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}