16 citations · 28 across the 14 of their papers we have counts for
4 papers · 2 filters
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 / λ…
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…
Space Efficient Multi-Dimensional Range Reporting
Marek Karpinski, Yakov Nekrich
We present a data structure that supports three-dimensional range reporting queries in time and uses $O(n\log^{1+\eps} n)$ space, where is…
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…