16 citations · 23 across the 7 of their papers we have counts for
9 papers
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…
1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two
Piotr Berman, Marek Karpinski, Alex Zelikovsky
We give a 1.25 approximation algorithm for the Steiner Tree Problem with distances one and two, improving on the best known bound for that problem.
Approximating Transitivity in Directed Networks
Piotr Berman, Bhaskar DasGupta, Marek Karpinski
We study the problem of computing a minimum equivalent digraph (also known as the problem of computing a strong transitive reduction) and its maximum objective function variant, wi…
The Mixing Time of Glauber Dynamics for Colouring Regular Trees
Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski
We consider Metropolis Glauber dynamics for sampling proper -colourings of the -vertex complete -ary tree when . We give both upper and lower bounds…
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…