16 citations · 23 across the 7 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2008
Low-Memory Adaptive Prefix Coding
Travis Gagie, Marek Karpinski, Yakov Nekrich
In this paper we study the adaptive prefix coding problem in cases where the size of the input alphabet is large. We present an online prefix coding algorithm that uses $O(σ^{1 / λ…
cs.DS2008
Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems
Marek Karpinski, Warren Schudy
We design a linear time approximation scheme for the Gale-Berlekamp Switching Game and generalize it to a wider class of dense fragile minimization problems including the Nearest C…
cs.DS2008★ 16 cited
Searching for Frequent Colors in Rectangles
Marek Karpinski, Yakov Nekrich
We study a new variant of colored orthogonal range searching problem: given a query rectangle all colors , such that at least a fraction of all points in are of colo…