Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems

Hossein Jowhari Mert Saglam Gábor Tardos

Published in: CoRR (2010)

Keyphrases

related problems
tight bounds
upper bound

linear programming
broadly applicable
data streams

range searching
stable marriage
linear program

lower bound
index structure