论文标题
在线度量匹配问题的两个变体的竞争分析
Competitive Analysis for Two Variants of Online Metric Matching Problem
论文作者
论文摘要
在本文中，我们研究了在线度量匹配问题的两个变体。第一个问题是在线公制匹配问题，其中所有服务器都位于公制空间中的两个位置之一。我们表明，一种简单的贪婪算法达到了3的竞争比，并具有匹配的下限。第二个问题是一条线上的在线设施分配问题，服务器具有容量，服务器和请求的一维线，并且任何两个连续的服务器之间的距离是相同的。我们显示下限$ 1+ \ \ sqrt {6} $ $（> 3.44948）$，$ \ frac {4+ \ sqrt {73}} {3} $ $（> 4.18133）$和$ \ frac {13} {3} {3} $（$ 4.3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333）分别为5。
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+ \sqrt{6}$ $(> 3.44948)$, $\frac{4+\sqrt{73}}{3}$ $(>4.18133)$ and $\frac{13}{3}$ $(>4.33333)$ on the competitive ratio when the numbers of servers are 3, 4 and 5, respectively.
