All reports by Author Bhaskar DasGupta:

__
TR07-119
| 5th December 2007
__

Piotr Berman, Bhaskar DasGupta, Marek Karpinski#### Approximating Transitive Reductions for Directed Networks

__
TR07-092
| 10th July 2007
__

Piotr Berman, Bhaskar DasGupta#### Approximating the Online Set Multicover Problems Via Randomized Winnowing

__
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

Piotr Berman, Bhaskar DasGupta, Marek Karpinski

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

Piotr Berman, Bhaskar DasGupta

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

Reka Albert, Bhaskar DasGupta, Riccardo Dondi, Eduardo D. Sontag

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