Matching on the line admits no o(√(log n))-competitive algorithm

12/31/2020

∙

by   Enoch Peserico, et al.

∙

0

∙

share

We present a simple proof that the competitive ratio of any randomized online matching algorithm for the line is at least √(log_2(n+1))/12 for all n=2^i-1: i∈ℕ.