论文标题
在线上匹配允许否$ o（\ sqrt {\ log n}）$ - 竞争算法
Matching on the line admits no $o(\sqrt{\log n})$-competitive algorithm
论文作者
论文摘要
我们提供了一个简单的证明，即该行的任何随机在线匹配算法的竞争比至少为$ \ sqrt {\ log_2（n \！+\！1）}/12 $，全部$ n = 2^i \！ - \！ - \！1：i \ in \ mathbb {n} $。
We present a simple proof that the competitive ratio of any randomized online matching algorithm for the line is at least $\sqrt{\log_2(n\!+\!1)}/12$ for all $n=2^i\!-\!1: i\in\mathbb{N}$.
