Lowerbounds for the online minimum matching problem on the line

摘要

We present lowerbounds for the competitive ratio of randomized algorithms on the online minimum matching problem on the line for both the minimum weight and bottleneck objectives. To the best of our knowledge, there is no established lowerbound for randomized algorithms for either objective on the line: we show a lowerbound of 2 for the minimum weight objective and a linear lowerbound for the bottleneck objective, hence proving that the bottleneck objective is a harder problem than the minimum weight objective on the line. We also present a tool for establishing a higher lower bound for the minimum weight objective.