Research PaperOpen Access

Competitive analysis for two variants of online metric matching problem

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

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

Search for more papers by this author

Shuichi Miyazaki

https://orcid.org/0000-0003-0369-1970

Academic Center for Computing and Media Studies, Kyoto University, Yoshida-Honmachi, Sakyo-ku, Kyoto 606-8501, Japan

E-mail Address: shuichi@media.kyoto-u.ac.jp

Search for more papers by this author

, and

Makoto Satake

Graduate School of Informatics, Kyoto University, Yoshida-Honmachi, Sakyo-ku, Kyoto 606-8501, Japan

E-mail Address: satake@net.ist.i.kyoto-u.ac.jp

Search for more papers by this author

https://doi.org/10.1142/S1793830921501561Cited by:7 (Source: Crossref)

Abstract

In the online metric matching problem, there are servers on a given metric space and requests are given one-by-one. The task of an online algorithm is to match each request immediately and irrevocably with one of the unused servers. In this paper, we pursue competitive analysis for two variants of the online metric matching problem. The first variant is a restriction where each server is placed at one of two positions, which is denoted by OMM( $2$ $2$ ). We show that a simple greedy algorithm achieves the competitive ratio of 3 for OMM( $2$ $2$ ). We also show that this greedy algorithm is optimal by showing that the competitive ratio of any deterministic online algorithm for OMM( $2$ $2$ ) is at least 3. The second variant is the online facility assignment problem on a line. In this problem, the metric space is a line, the servers have capacities, and the distances between any two consecutive servers are the same. We denote this problem by OFAL( $k$ $k$ ), where $k$ $k$ is the number of servers. We first observe that the upper and lower bounds for OMM( $2$ $2$ ) also hold for OFAL( $2$ $2$ ), so the competitive ratio for OFAL( $2$ $2$ ) is exactly 3. We then show lower bounds on the competitive ratio $1 + \sqrt{6}$ $1 + \sqrt{6}$ $(> 3.44948)$ $(> 3.44948)$ , $\frac{4 + \sqrt{73}}{3}$ $\frac{4 + \sqrt{73}}{3}$ $(> 4.18133)$ $(> 4.18133)$ and $\frac{13}{3}$ $\frac{13}{3}$ $(> 4.33333)$ $(> 4.33333)$ for OFAL( $3$ $3$ ), OFAL( $4$ $4$ ) and OFAL( $5$ $5$ ), respectively.

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, N. Barcelo, M. Nugent, K. Pruhs and M. Scquizzato, A $o (n)$ $o (n)$ -competitive deterministic algorithm for online matching on a line, in Proc. Int. Workshop on Approximation and Online Algorithms (Springer, 2014), pp. 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 (Springer, 2018), pp. 52–65. Crossref, Google Scholar
4. I. Ashlagi, Y. Azar, M. Charikar, A. Chiplunkar, O. Geri, H. Kaplan, R. Makhijani, Y. Wang and R. Wattenhofer, Min-cost bipartite perfect matching with delays, in Proc. APPROX/RANDOM (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 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. Symp. Discrete Algorithms (ACM, 2017), pp. 1051–1061. Crossref, Google Scholar
6. Y. Azar and A. J. Fanani, Deterministic min-cost matching with delays, in Proc. Int. Workshop on Approximation and Online Algorithms (Springer, 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. European Symp. Algorithms (Springer, 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. Int. Workshop on Approximation and Online Algorithms (Springer, 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. Int. Workshop on Approximation and Online Algorithms (Springer, 2017), pp. 132–146. Google Scholar
10. Y. Emek, S. Kutten and R. Wattenhofer, Online matching: Haste makes waste! in Proc. Symp. Theory of Computing (ACM, 2016), pp. 333–334. Crossref, Google Scholar
11. Y. Emek, Y. Shapiro and Y. Wang, Minimum cost perfect matching with delays for two sources, Int. Conf. Algorithms and Complexity (Springer, 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, Int. Colloquium on Automata, Languages, and Programming (Springer, 2012), pp. 424–435. Crossref, Google Scholar
14. B. Kalyanasundaram and K. Pruhs, Online weighted matching, J. Algorithms 14(3) (1993) 478–488. Crossref, Google Scholar
15. B. Kalyanasundaram and K. Pruhs, Online network optimization problems, Online Algorithms, Lecture Notes in Computer Science, Vol. 1442 (Springer, 1998), pp. 268–280. Crossref, Google Scholar
16. R. M. Karp, U. V. Vazirani and V. V. Vazirani, An optimal algorithm for on-line bipartite matching, in Proc. Symp. Theory of Computing (ACM, 1990), pp. 352–358. Crossref, Google Scholar
17. S. Khuller, S. G. Mitchell and V. V. Vazirani, On-line algorithms for weighted bipartite matching and stable marriages, Theoretical Computer Science 127(2) (1994) 255–267. Crossref, Google Scholar
18. E. Koutsoupias and A. Nanavati, The online matching problem on a line, in Proc. Int. Workshop on Approximation and Online Algorithms (Springer, 2004), pp. 179–191. Crossref, Google Scholar
19. X. Liu, Z. Pan, Y. Wang and R. Wattenhofer, Impatient online matching, in Proc. Int. Symp. Algorithms and Computation (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018), pp. 62:1–62:12. Google Scholar
20. A. Mehta, Online matching and ad allocation, Found. Trends Theor. Comput. Sci. 8(4) (2012) 265–368. Crossref, Google Scholar
21. A. Meyerson, A. Nanavati and L. J. Poplawski, Randomized online algorithms for minimum metric bipartite matching, in Proc. Symp. Discrete Algorithm (ACM, 2006), pp. 954–959. Crossref, Google Scholar
22. S. A. Muttakee, A. R. Ahmed and M. S. Rahman, New results and bounds on online facility assignment problem, preprint (2020), arXiv:2009.01446. Google Scholar
23. K. Nayyar and S. Raghvendra, An input sensitive online algorithm for the metric bipartite matching problem, in Proc. Symp. Foundations of Computer Science (IEEE, 2017), pp. 505–515. Crossref, Google Scholar
24. E. Peserico and M. Scquizzato, Matching on the line admits no $o (\sqrt{log n})$ $o (\sqrt{log n})$ -competitive algorithm, in Proc. Int. Colloquium on Automata, Languages, and Programming (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2021), pp. 103:1–103:3. Google Scholar
25. S. Raghvendra, A robust and optimal online algorithm for minimum metric bipartite matching, in Proc. APPROX/RANDOM, Vol. 60 (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016), pp. 18:1–18:16. Google Scholar
26. S. Raghvendra, Optimal analysis of an online algorithm for the bipartite matching problem on a line, in Proc. Int. Symp. Computational Geometry (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018), pp. 67:1–67:14. Google Scholar
27. 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

Vol. 13, No. 06

Metrics

Downloaded 406 times

History

Received 29 January 2021

Revised 20 April 2021

Accepted 1 June 2021

Published: 10 July 2021

Information

This is an Open Access article published by World Scientific Publishing Company. It is distributed under the terms of the Creative Commons Attribution 4.0 (CC BY) License which permits use, distribution and reproduction in any medium, provided the original work is properly cited.

Keywords

PDF download

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Competitive analysis for two variants of online metric matching problem

Abstract

Recommended