{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:24:52Z","timestamp":1753885492534,"version":"3.41.2"},"reference-count":29,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","funder":[{"name":"JSPS KAKENHI","award":["JP20K11677"],"award-info":[{"award-number":["JP20K11677"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:p> In the online facility assignment problem [Formula: see text], there exist [Formula: see text] servers [Formula: see text] on a metric space where each [Formula: see text] has an integer capacity [Formula: see text] and a request arrives one-by-one. The task of an online algorithm is to irrevocably match a current request with one of the servers with vacancies before the next request arrives. As special cases for [Formula: see text], we consider [Formula: see text] on a line\u200a, which is denoted by [Formula: see text] and [Formula: see text], where the latter is the case of [Formula: see text] with equidistant servers. In this paper, we perform the competitive analysis for the above problems. As a natural generalization of the greedy algorithm grdy, we introduce a class of algorithms called MPFS (Most Preferred Free Servers) and show that any MPFS algorithm has the capacity-insensitive property, i.e., for any MPFS algorithm alg for [Formula: see text], if alg is [Formula: see text]-competitive when [Formula: see text], then alg is [Formula: see text]-competitive for general [Formula: see text]. By applying the capacity-insensitive property of the greedy algorithm grdy, we derive the matching upper and lower bounds [Formula: see text] on the competitive ratio of grdy for [Formula: see text]. To investigate the capability of MPFS algorithms, we show that the competitive ratio of any MPFS algorithm alg for [Formula: see text] is at least [Formula: see text]. Then, we propose a new MPFS algorithm idas (Interior Division for Adjacent Servers) for [Formula: see text] and show that the competitive ratio of idas for [Formula: see text] is at most [Formula: see text], i.e., idas for [Formula: see text] is best possible in all the MPFS algorithms. We also give numerical experiments to investigate the performance of idas and grdy and show that idas performs better than grdy for distribution of request sequences with locality. <\/jats:p>","DOI":"10.1142\/s179383092350057x","type":"journal-article","created":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T06:26:59Z","timestamp":1685600819000},"source":"Crossref","is-referenced-by-count":2,"title":["Capacity-insensitive algorithms for online facility assignment problems on a line"],"prefix":"10.1142","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8101-4153","authenticated-orcid":false,"given":"Tsubasa","family":"Harada","sequence":"first","affiliation":[{"name":"Department of Mathematical and Computing Science, Tokyo Institute of Technology, 2-12-1 Ookayama, Meguro-ku, Tokyo 152-8552, Japan"}]},{"given":"Toshiya","family":"Itoh","sequence":"additional","affiliation":[{"name":"Department of Mathematical and Computing Science, Tokyo Institute of Technology, 2-12-1 Ookayama, Meguro-ku, Tokyo 152-8552, Japan"}]},{"given":"Shuichi","family":"Miyazaki","sequence":"additional","affiliation":[{"name":"Graduate School of Information Science, University of Hyogo, 8-2-1 Gakuennishi-machi, Nishi-ku, Kobe, Hyogo 651-2197, Japan"}]}],"member":"219","published-online":{"date-parts":[[2023,7,19]]},"reference":[{"key":"S179383092350057XBIB001","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.08.011"},{"key":"S179383092350057XBIB002","first-page":"11","volume-title":"Proc. WAOA 2012","author":"Antoniadis A.","year":"2014"},{"key":"S179383092350057XBIB003","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-77404-6_5"},{"key":"S179383092350057XBIB004","first-page":"1:1","volume-title":"Proc. APPROX\/RANDOM 2017","author":"Ashlagi I.","year":"2017"},{"key":"S179383092350057XBIB005","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.67"},{"key":"S179383092350057XBIB006","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-04693-4_2"},{"key":"S179383092350057XBIB007","first-page":"522","volume-title":"Proc. ESA 2007","author":"Bansal N.","year":"2007"},{"key":"S179383092350057XBIB008","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-04693-4_4"},{"key":"S179383092350057XBIB009","first-page":"132","volume-title":"Proc. WAOA 2017","author":"Bienkowski M.","year":"2017"},{"key":"S179383092350057XBIB010","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897557"},{"key":"S179383092350057XBIB011","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57586-5_18"},{"key":"S179383092350057XBIB012","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.028"},{"key":"S179383092350057XBIB013","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_36"},{"key":"S179383092350057XBIB014","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-79711-3"},{"key":"S179383092350057XBIB015","doi-asserted-by":"publisher","DOI":"10.1142\/S1793830921501561"},{"key":"S179383092350057XBIB016","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1026"},{"key":"S179383092350057XBIB017","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480198342310"},{"key":"S179383092350057XBIB019","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100262"},{"key":"S179383092350057XBIB020","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90042-6"},{"key":"S179383092350057XBIB021","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24592-6_14"},{"key":"S179383092350057XBIB022","doi-asserted-by":"publisher","DOI":"10.1145\/210118.210128"},{"key":"S179383092350057XBIB023","first-page":"62:1","volume-title":"Proc. ISAAC 2018","author":"Liu X.","year":"2018"},{"key":"S179383092350057XBIB024","doi-asserted-by":"publisher","DOI":"10.1561\/0400000057"},{"key":"S179383092350057XBIB025","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109662"},{"key":"S179383092350057XBIB027","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.53"},{"key":"S179383092350057XBIB028","first-page":"103:1","volume-title":"Proc. ICALP 2021","author":"Peserico E.","year":"2021"},{"key":"S179383092350057XBIB029","first-page":"18:1","volume-title":"Proc. APPROX\/RANDOM 2016","volume":"60","author":"Raghvendra S.","year":"2016"},{"key":"S179383092350057XBIB030","first-page":"67:1","volume-title":"Proc. SoCG 2018","author":"Raghvendra S.","year":"2018"},{"key":"S179383092350057XBIB032","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S179383092350057X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,8]],"date-time":"2024-05-08T03:29:49Z","timestamp":1715138989000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S179383092350057X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,19]]},"references-count":29,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["10.1142\/S179383092350057X"],"URL":"https:\/\/doi.org\/10.1142\/s179383092350057x","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"type":"print","value":"1793-8309"},{"type":"electronic","value":"1793-8317"}],"subject":[],"published":{"date-parts":[[2023,7,19]]},"article-number":"2350057"}}