Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2009 Copyright 2009 Universität Bonn, Institut für Informatik, Abt. V


Approximating Transitive Reductions for Directed Networks (Revised Version)
Piotr Berman, Bhaskar DasGupta and Marek Karpinski
[Download PostScript] [Download PDF]

We consider minimum equivalent digraph problem, its maximum optimization variant and some non-trivial extensions of these two types of problems motivated by biological and social network applications. We provide 3/2-approximation algorithms for all the minimization problems and 2-approximation algorithms for all the maximization problems using appropriate primal-dual polytopes. We also show lower bounds on the integrality gap of the polytope to provide some intuition on the final limit of such approaches. Furthermore, we provide APX-hardness result for all those problems even if the length of all simple cycles is bounded by 5.

Last Change: 11/05/14 at 10:50:27
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope