Competitive analysis for two variants of online metric matching problem
Competitive analysis for two variants of online metric matching problem
复制标题
在线度量匹配问题的两种变体的竞争分析
DOI：
10.1142/s1793830921501561
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Satake Makoto
中科院分区：
文献类型：
--
作者：
Itoh Toshiya;Miyazaki Shuichi;Satake Makoto
在在线指标匹配问题中，在给定的指标空间上有多个服务器，并且请求被逐个给予。在线算法的任务是立即将每个请求与其中一个未使用的服务器进行不可撤销的匹配。在本文中，我们对在线度量匹配问题的两种变体进行了竞争分析。第一个变体是一种限制，其中每个服务器被放置在两个位置中的一个位置，这由OMM()表示。我们证明了一个简单的贪婪算法可以达到OMM()的3倍的竞争比。我们还证明了该贪婪算法是最优的，证明了OMM()的任一确定性在线算法的竞争比至少为3。第二个变体是在线设施分配问题。在这个问题中，度量空间是一条直线，服务器有容量，任意两个连续的服务器之间的距离是相同的。我们用ofal()表示这个问题，其中是服务器的数量。我们首先观察到OMM()的上界和下界对ofal()也成立，所以ofal()的竞争比正好是3。然后，我们分别给出了ofal()、ofal()和ofal()的竞争比的下界。
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(). We show that a simple greedy algorithm achieves the competitive ratio of 3 for OMM(). We also show that this greedy algorithm is optimal by showing that the competitive ratio of any deterministic online algorithm for OMM() 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(), whereis the number of servers. We first observe that the upper and lower bounds for OMM() also hold for OFAL(), so the competitive ratio for OFAL() is exactly 3. We then show lower bounds on the competitive ratio,andfor OFAL(), OFAL() and OFAL(), respectively.