Matching on the line admits no $o(\sqrt{\log n})$ -competitive algorithm

preprint2020arXivOpen access

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}$ .

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Write a reviewWrite

No reviews yet.

Add a commentWrite

No comments yet.

Matching on the line admits no $o(\sqrt{\log n})$ -competitive algorithm

Abstract

Connections

Building this map preview

Reviews 0

Discussion 0

Matching on the line admits no o(log⁡n)o(\sqrt{\log n})o(logn​)-competitive algorithm

Abstract

Connections

Building this map preview

Reviews 0

Discussion 0

Matching on the line admits no $o(\sqrt{\log n})$ -competitive algorithm