Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Approximation Factors:
TR07-119 | 5th December 2007
Piotr Berman, Bhaskar DasGupta, Marek Karpinski

Approximating Transitive Reductions for Directed Networks

We consider <i>minimum equivalent digraph</i> (<i>directed network</i>) problem (also known as the <i>strong transitive reduction</i>), its maximum optimization variant, and some extensions of those two types of problems. We prove the existence of polynomial time approximation algorithms with ratios 1.5 for all the minimization problems and 2 for all the ... more >>>

TR08-094 | 10th October 2008
Piotr Berman, Marek Karpinski, Alexander Zelikovsky

1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two

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.

more >>>

ISSN 1433-8092 | Imprint