We prove a lower bound ρ ≥ 9.001 for the i competitive ratio of the so-called online matching problem on a line. As a consequence, the online matching problem is revealed to be strictly more difficult than the “cow problem”.
|Name||Electronic Notes in Theoretical Computer Science (ENTCS)|
|Workshop||2nd Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2003|
|Period||14/05/03 → 16/05/03|
- Competitive Analysis
- On-line algorithms