16 citations · 28 across the 14 of their papers we have counts for
6 papers · 2 filters
A Factor 3/2 Approximation for Generalized Steiner Tree Problem with Distances One and Two
Piotr Berman, Marek Karpinski, Alex Zelikovsky
We design a 3/2 approximation algorithm for the Generalized Steiner Tree problem (GST) in metrics with distances 1 and 2. This is the first polynomial time approximation algorithm…
Trading GRH for algebra: algorithms for factoring polynomials and related structures
Gábor Ivanyos, Marek Karpinski, Lajos Rónyai +1
In this paper we develop techniques that eliminate the need of the Generalized Riemann Hypothesis (GRH) from various (almost all) known results about deterministic polynomial facto…
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…
Schemes for Deterministic Polynomial Factoring
Gábor Ivanyos, Marek Karpinski, Nitin Saxena
In this work we relate the deterministic complexity of factoring polynomials (over finite fields) to certain combinatorial objects we call m-schemes. We extend the known conditiona…