Title of article
Average Complexity of Addition Updates and Range Queries over an Array using Graphs
Author/Authors
Toni، نويسنده , , A.، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2003
Pages
6
From page
117
To page
122
Abstract
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”.
Keywords
range queries , semi-group model , average complexity
Journal title
Electronic Notes in Discrete Mathematics
Serial Year
2003
Journal title
Electronic Notes in Discrete Mathematics
Record number
1453471
Link To Document