Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Bhaskar DasGupta:

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 >>>

TR07-092 | 10th July 2007
Piotr Berman, Bhaskar DasGupta

Approximating the Online Set Multicover Problems Via Randomized Winnowing

In this paper, we consider the weighted online set k-multicover problem. In this problem, we have an universe V of elements, a family SS of subsets of V with a positive real cost for every S\in SS, and a ``coverage factor'' (positive integer) k. A subset \{i_0,i_1,\ldots\ \subseteq V of ... more >>>

TR06-010 | 1st December 2005
Reka Albert, Bhaskar DasGupta, Riccardo Dondi, Eduardo D. Sontag

Inferring (Biological) Signal Transduction Networks via Transitive Reductions of Directed Graphs

In this paper we consider the p-ary transitive reduction (TR<sub>p</sub>) problem where p>0 is an integer; for p=2 this problem arises in inferring a sparsest possible (biological) signal transduction network consistent with a set of experimental observations with a goal to minimize false positive inferences even if risking false negatives. ... more >>>

ISSN 1433-8092 | Imprint