ダウンロード数: 42
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
s1793830921501561.pdf | 478.96 kB | Adobe PDF | 見る/開く |
タイトル: | Competitive analysis for two variants of online metric matching problem |
著者: | Itoh, Toshiya Miyazaki, Shuichi Satake, Makoto |
著者名の別形: | 宮崎, 修一 佐竹, 誠 |
キーワード: | Online algorithm competitive analysis online metric matching online facility assignment problem |
発行日: | Dec-2021 |
出版者: | World Scientific Pub Co Pte Ltd |
誌名: | Discrete Mathematics, Algorithms and Applications |
巻: | 13 |
号: | 6 |
論文番号: | 2150156 |
抄録: | 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). We show that a simple greedy algorithm achieves the competitive ratio of 3 for OMM(2). We also show that this greedy algorithm is optimal by showing that the competitive ratio of any deterministic online algorithm for OMM(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), where k is the number of servers. We first observe that the upper and lower bounds for OMM(2) also hold for OFAL(2), so the competitive ratio for OFAL(2) is exactly 3. We then show lower bounds on the competitive ratio 1+6–√(>3.44948), 4+73√3(>4.18133) and 133(>4.33333) for OFAL(3), OFAL(4) and OFAL(5), respectively. |
著作権等: | © The Author(s) 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. |
URI: | http://hdl.handle.net/2433/276424 |
DOI(出版社版): | 10.1142/S1793830921501561 |
出現コレクション: | 学術雑誌掲載論文等 |
このアイテムは次のライセンスが設定されています: クリエイティブ・コモンズ・ライセンス