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
85303

13.05.2009

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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V