Research PaperNo Access

Capacity-insensitive algorithms for online facility assignment problems on a line

Department of Mathematical and Computing Science, Tokyo Institute of Technology, 2-12-1 Ookayama, Meguro-ku, Tokyo 152-8552, Japan

E-mail Address: harada.t.ak@m.titech.ac.jp

Search for more papers by this author

Toshiya Itoh

Department of Mathematical and Computing Science, Tokyo Institute of Technology, 2-12-1 Ookayama, Meguro-ku, Tokyo 152-8552, Japan

E-mail Address: titoh@c.titech.ac.jp

Search for more papers by this author

, and

Shuichi Miyazaki

Graduate School of Information Science, University of Hyogo, 8-2-1 Gakuennishi-machi, Nishi-ku, Kobe, Hyogo 651-2197, Japan

E-mail Address: shuichi@sis.u-hyogo.ac.jp

Search for more papers by this author

https://doi.org/10.1142/S179383092350057XCited by:2 (Source: Crossref)

Abstract

In the online facility assignment problem $OFA (k, {c_{i}}_{i = 1}^{k})$ $OFA (k, {c_{i}}_{i = 1}^{k})$ , there exist $k$ $k$ servers $s_{1}, \dots, s_{k}$ $s_{1}, \dots, s_{k}$ on a metric space where each $s_{i}$ $s_{i}$ has an integer capacity $c_{i}$ $c_{i}$ 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 $OFA (k, {c_{i}}_{i = 1}^{k})$ $OFA (k, {c_{i}}_{i = 1}^{k})$ , we consider $OFA (k, {c_{i}}_{i = 1}^{k})$ $OFA (k, {c_{i}}_{i = 1}^{k})$ on a line , which is denoted by $OFAL (k, {c_{i}}_{i = 1}^{k})$ $OFAL (k, {c_{i}}_{i = 1}^{k})$ and ${OFAL}_{eq} (k, {c_{i}}_{i = 1}^{k})$ ${OFAL}_{eq} (k, {c_{i}}_{i = 1}^{k})$ , where the latter is the case of $OFAL (k, {c_{i}}_{i = 1}^{k})$ $OFAL (k, {c_{i}}_{i = 1}^{k})$ 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 $OFA (k, {c_{i}}_{i = 1}^{k})$ $OFA (k, {c_{i}}_{i = 1}^{k})$ , if alg is $c$ $c$ -competitive when $c_{1} = \dots = c_{k} = 1$ $c_{1} = \dots = c_{k} = 1$ , then alg is $c$ $c$ -competitive for general ${c_{i}}_{i = 1}^{k}$ ${c_{i}}_{i = 1}^{k}$ . By applying the capacity-insensitive property of the greedy algorithm grdy, we derive the matching upper and lower bounds $4 k - 5$ $4 k - 5$ on the competitive ratio of grdy for ${OFAL}_{eq} (k, {c_{i}}_{i = 1}^{k})$ ${OFAL}_{eq} (k, {c_{i}}_{i = 1}^{k})$ . To investigate the capability of MPFS algorithms, we show that the competitive ratio of any MPFS algorithm alg for ${OFAL}_{eq} (k, {c_{i}}_{i = 1}^{k})$ ${OFAL}_{eq} (k, {c_{i}}_{i = 1}^{k})$ is at least $2 k - 1$ $2 k - 1$ . Then, we propose a new MPFS algorithm idas (Interior Division for Adjacent Servers) for $OFAL (k, {c_{i}}_{i = 1}^{k})$ $OFAL (k, {c_{i}}_{i = 1}^{k})$ and show that the competitive ratio of idas for ${OFAL}_{eq} (k, {c_{i}}_{i = 1}^{k})$ ${OFAL}_{eq} (k, {c_{i}}_{i = 1}^{k})$ is at most $2 k - 1$ $2 k - 1$ , i.e., idas for ${OFAL}_{eq} (k, {c_{i}}_{i = 1}^{k})$ ${OFAL}_{eq} (k, {c_{i}}_{i = 1}^{k})$ 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.

Communicated by Dachuan Xu

Keywords:

AMSC: 68W27, 68W40

References

1. A. R. Ahmed, M. S. Rahman and S. G. Kobourov , Online facility assignment, Theor. Comput. Sci. 806 (2020) 455–467. Crossref, Google Scholar
2. A. Antoniadis, M. Barcelo, M. Nugent, N. Pruhs and M. Scquizzato , A $o (n)$ $o (n)$ -competitive deterministic algorithm for online matching on a line, in Proc. WAOA 2012 (2014) 11–22. Google Scholar
3. A. Antoniadis, C. Fischer and A. Tönnis , A collection of lower bounds for online matching on the line, in Proc. LATIN 2018 (Buenos Aires, Argentina, 2018), pp. 52–65. Crossref, Google Scholar
4. I. Ashlagi, Y. Azar, A. Chiplunkar, O. Geri, H. Kaplan, R. Makhijani, Y. Wang and R. Wattenhofer , Min-cost bipartite perfect matching with delays, in Proc. APPROX/RANDOM 2017 (Berkeley, CA, USA, 2017), pp. 1:1–1:20. Google Scholar
5. Y. Azar, A. Chiplunkar and H. Kaplan , Polylogarithmic bounds on the competitiveness of min-cost perfect matching with delays, in Proc. SODA 2017 (Barcelona, Spain, 2017), pp. 1051–1061. Crossref, Google Scholar
6. Y. Azar and A. Fanani , Deterministic min-cost matching with delays, in Proc. WAOA 2018 (Helsinki, Finland, 2018), pp. 21–35. Crossref, Google Scholar
7. N. Bansal, N. Buchbinder, A. Gupta and J. Naor , An $O ({log}^{2} k)$ $O ({log}^{2} k)$ -competitive algorithm for metric bipartite matching, in Proc. ESA 2007 (Eilat, Israel, 2007), pp. 522–533. Google Scholar
8. M. Bienkowski, A. Kraska, H. Liu and P. Schmidt , A primal-dual online deterministic algorithm for matching with delays, in Proc. WAOA 2018 (Helsinki, Finland, 2018), pp. 51–68. Crossref, Google Scholar
9. M. Bienkowski, A. Kraska and P. Schmidt , A match in time saves nine: Deterministic online matching with delays, in Proc. WAOA 2017 (Vienna, Austria, 2017), pp. 132–146. Google Scholar
10. Y. Emek, S. Kutten and R. Wattenhofer , Online matching: Haste makes waste! in Proc. STOC 2016 (Cambridge, MA, USA, 2016), pp. 333–334. Crossref, Google Scholar
11. Y. Emek, Y. Shapiro and Y. Wang , Minimum cost perfect matching with delays for two sources, in CIAC 2017 (Athens, Greece, 2017), pp. 209–221. Crossref, Google Scholar
12. B. Fuchs, W. Hochstättler and W. Kern , Online matching on a line, Theor. Comput. Sci. 332 (2005) 251–264. Crossref, Google Scholar
13. A. Gupta and K. Lewi , The online metric matching problem for doubling metrics, in ICALP 2012 (Warwick, UK, 2012), pp. 424–435. Crossref, Google Scholar
14. J. M. Harris, J. L. Hirst and M. J. Mossinghoff , Combinatorics and Graph Theory, 2nd edn. (Springer, 2008). Crossref, Google Scholar
15. T. Itoh, S. Miyazaki and M. Satake , Competitive analysis for two variants of online metric matching problem, Discrete Math. Algorithms Appl. 13(6) (2021) 2150156:1–2150156:16. Link, Google Scholar
16. B. Kalyanasundaram and K. Pruhs , Online weighted matching, J. Algorithms 14(3) (1993) 478–488. Crossref, Google Scholar
17. B. Kalyanasundaram and K. Pruhs , The online transportation problem, SIAM J. Discrete Math. 13(3) (2000) 370–383. Crossref, Google Scholar
18. B. Kalyanasundaram and K. Pruhs, Online network optimization problems, Online algorithms: The state of the art (2005), pp. 268–280. Google Scholar
19. R. M. Karp, U. V. Vazirani and V. V. Vazirani , An optimal algorithm for on-line bipartite matching, in Proc. STOC 1990 (Baltimore, Maryland, USA, 1990), pp. 352–358. Crossref, Google Scholar
20. S. Khuller, S. G. Mitchell and V. V. Vazirani , On-line algorithms for weighted bipartite matching and stable marriages, Theor. Comput. Sci. 127(2) (1994) 255–267. Crossref, Google Scholar
21. E. Koutsoupias and A. Nanavati , The online matching problem on a line, in Proc. WAOA 2003 (Budapest, Hungary, 2004), pp. 179–191. Crossref, Google Scholar
22. E. Koutsoupias and C. H. Papadimitriou , On the $k$ $k$ -server conjecture, J. ACM 42(5) (1995) 971–983. Crossref, Google Scholar
23. X. Liu, Z. Pan, Y. Wang and R. Wattenhofer , Impatient online matching, in Proc. ISAAC 2018 (Jiaoxi, Yilan, Taiwan, 2018), pp. 62:1–62:12. Google Scholar
24. A. Mehta , Online matching and ad allocation, Found. Trends Theor. Comput. Sci. 8(4) (2012) 265–368. Crossref, Google Scholar
25. A. Meyerson, A. Nanavati and L. J. Poplawski , Randomized online algorithms for minimum metric bipartite matching, in Proc. SODA 2006 (Miami, Florida, USA, 2006), pp. 954–959. Crossref, Google Scholar
26. S. A. Muttakee, A. R. Ahmed and M. S. Rahman, New results and bounds on online facility assignment problem, preprint (2020), arXiv:2009.01446.40. Google Scholar
27. K. Nayyar and S. Raghvendra , An input sensitive online algorithm for the metric bipartite matching problem, in Proc. FOCS 2017 (Berkeley, CA, USA, 2017), pp. 505–515. Crossref, Google Scholar
28. E. Peserico and M. Scquizzato , Matching on the line admits no $o (\sqrt{log n})$ $o (\sqrt{log n})$ -competitive algorithm, in Proc. ICALP 2021 (2021), pp. 103:1–103:3. Google Scholar
29. S. Raghvendra , A robust and optimal online algorithm for minimum metric bipartite matching, in Proc. APPROX/RANDOM 2016, Vol. 60 (2016), pp. 18:1–18:16. Google Scholar
30. S. Raghvendra , Optimal analysis of an online algorithm for the bipartite matching problem on a line, in Proc. SoCG 2018 (Budapest, Hungary, 2018), pp. 67:1–67:14. Google Scholar
31. M. Satake, Competitive analysis for the Online facility assignment problem on a line, Master Thesis, Graduate School of Informatics, Kyoto University (2022). Google Scholar
32. D. D. Sleator and R. E. Tarjan , Amortized efficiency of list update and paging rules, Commun. ACM 28(2) (1985) 202–208. Crossref, Google Scholar