Matching on the Line Admits no \(o(\sqrt {\log n})\) -Competitive Algorithm
Matching on the Line Admits no \(o(\sqrt {\log n})\) -Competitive Algorithm
复制标题
线上匹配不承认 (o(sqrt {log n})) -竞争算法
DOI：
--
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Michele Scquizzato
中科院分区：
文献类型：
--
作者：
E. Peserico;Michele Scquizzato
我们给出了一个简单的证明：对于任何n=2i-1：i∈ℕ，这条线的随机在线匹配算法都不能与一个不经意的对手竞争。这是该问题的第一个超恒定下界，并作为推论证明了最近关于一般空间上可实现的拓扑参数竞争的猜想。
We present a simple proof that no randomized online matching algorithm for the line can be \((\sqrt {\log _2(n+1)}/15)\) -competitive against an oblivious adversary for any n = 2i - 1 : i ∈ ℕ. This is the first super-constant lower bound for the problem, and disproves as a corollary a recent conjecture on the topology-parametrized competitiveness achievable on generic spaces.
在线最低成本匹配，在线追索
DOI：
10.4230/lipics.approx/random.2020.37
发表时间：
--
期刊：
影响因子：
--
作者：
N. Megow;L. Nölke.
通讯作者：
L. Nölke.
随机在线指标匹配
DOI：
10.4230/lipics.icalp.2019.67
发表时间：
2019
期刊：
and Programming
影响因子：
--
作者：
Gupta, Anupam;Guruganesh, Guru;Peng, Binghui;Wajc, David
通讯作者：
Wajc, David