2020/08/19 by Toshiya Itoh, Shuichi Miyazaki, Itoh, Toshiya +3
Computer Science · #68W27 #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2008.08415
openalex publication_date 2020/08/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we study two variants of the online metric matching problem. The first problem is the online metric matching problem where all the servers are placed at one of two positions in the metric space. We show that a simple greedy algorithm achieves the competitive ratio of 3 and give a matching lower bound. The second problem is the online facility assignment problem on a line, where servers have capacities, servers and requests are placed on 1-dimensional line, and the distances between any two consecutive servers are the same. We show lower bounds 1+ √(6) (> 3.44948), (4+√(73))/(3) (>4.18133) and (13)/(3) (>4.33333) on the competitive ratio when the numbers of servers are 3, 4 and 5, respectively.