The Online Matching Problem on a Line
The Online Matching Problem on a Line
复制标题
线上在线匹配问题
DOI：
10.1007/978-3-540-24592-6_14
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Akash Nanavati
中科院分区：
文献类型：
--
作者：
E. Koutsoupias;Akash Nanavati
研究了度量空间为单直线时的在线匹配问题。对于这种情况，离线匹配问题是微不足道的，但在线问题一直是开放的，并且最知名的竞争比是微不足道的Θ（n），其中n是请求的数量。证明了广义功函数算法对该问题具有常数竞争比。我们证明了它实际上是Ω（logn）和O（n），并通过建立解的一些结构性质，在证明一个更好的上界方面取得了一些进展。我们的上限技术不使用潜在的功能，但它重新分配的方式，与离线成本的比较变得更加直接的在线成本。
We study the online matching problem when the metric space is a single straight line. For this case, the offline matching problem is trivial but the online problem has been open and the best known competitive ratio was the trivial Θ(n) where n is the number of requests. It was conjectured that the generalized Work Function Algorithm has constant competitive ratio for this problem. We show that it is in fact Ω(logn) and O(n), and make some progress towards proving a better upper bound by establishing some structural properties of the solutions. Our technique for the upper bound doesn’t use a potential function but it reallocates the online cost in a way that the comparison with the offline cost becomes more direct.