Document

**Published in:** LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

In this paper, we study a class of set cover problems that satisfy a special property which we call the small neighborhood cover property.
This class encompasses several well-studied problems including vertex cover, interval cover, bag interval cover and tree cover. We design unified distributed and parallel algorithms that can handle any set cover problem falling under the above framework and yield constant factor approximations. These algorithms run in polylogarithmic communication rounds in the distributed setting and are in NC, in the parallel setting.

Archita Agarwal, Venkatesan T. Chakaravarthy, Anamitra Roy Choudhury, Sambuddha Roy, and Yogish Sabharwal. Distributed and Parallel Algorithms for Set Cover Problems with Small Neighborhood Covers. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 249-261, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.FSTTCS.2013.249, author = {Agarwal, Archita and Chakaravarthy, Venkatesan T. and Choudhury, Anamitra Roy and Roy, Sambuddha and Sabharwal, Yogish}, title = {{Distributed and Parallel Algorithms for Set Cover Problems with Small Neighborhood Covers}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {249--261}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.249}, URN = {urn:nbn:de:0030-drops-43775}, doi = {10.4230/LIPIcs.FSTTCS.2013.249}, annote = {Keywords: approximation algorithms, set cover problem, tree cover} }

Document

**Published in:** LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

We consider the Knapsack Covering problem subject to a matroid constraint. In this problem, we are given an universe U of n items where item i has attributes: a cost c(i) and a size s(i). We also have a demand D. We are also given a matroid M = (U, I) on the set U. A feasible solution S to the problem is one such that (i) the cumulative size of the items chosen is at least D, and (ii) the set S is independent in the matroid M (i.e. S is in I). The objective is to minimize the total cost of the items selected, sum_{i in S}c(i).
Our main result proves a 2-factor approximation for this problem.
The problem described above falls in the realm of mixed packing covering problems. We also consider packing extensions of certain other covering problems and prove that in such cases it is not possible to derive any constant factor pproximations.

Venkatesan T. Chakaravarthy, Anamitra Roy Choudhury, Sivaramakrishnan R. Natarajan, and Sambuddha Roy. Knapsack Cover Subject to a Matroid Constraint. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 275-286, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{chakaravarthy_et_al:LIPIcs.FSTTCS.2013.275, author = {Chakaravarthy, Venkatesan T. and Choudhury, Anamitra Roy and Natarajan, Sivaramakrishnan R. and Roy, Sambuddha}, title = {{Knapsack Cover Subject to a Matroid Constraint}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {275--286}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.275}, URN = {urn:nbn:de:0030-drops-43795}, doi = {10.4230/LIPIcs.FSTTCS.2013.275}, annote = {Keywords: Approximation Algorithms, LP rounding, Matroid Constraints, Knapsack problems} }

Document

**Published in:** LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

In this paper, we consider the problem of choosing a minimum cost set of resources for executing a specified set of jobs. Each input job is an interval, determined by its start-time and end-time. Each resource is also an interval determined by its start-time and end-time; moreover, every resource has a capacity and a cost associated with it. We consider two versions of this problem.
In the partial covering version, we are also given as input a number k, specifying the number of jobs that must be performed. The goal is to choose $k$ jobs and find a minimum cost set of resources to perform the chosen k jobs (at any point of time the capacity of the chosen set of resources should be sufficient to execute the jobs active at that time). We present an O(log n)-factor approximation algorithm for this problem.
We also consider the prize collecting version, wherein every job also has a penalty associated with it. The feasible solution consists of a subset of the jobs, and a set of resources, to perform the chosen subset of jobs. The goal is to find a feasible solution that minimizes the sum of the costs of the selected resources and the penalties of the jobs that are not selected. We present a constant factor approximation algorithm for this problem.

Venkatesan T. Chakaravarthy, Arindam Pal, Sambuddha Roy, and Yogish Sabharwal. Scheduling Resources for Executing a Partial Set of Jobs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 199-210, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{chakaravarthy_et_al:LIPIcs.FSTTCS.2012.199, author = {Chakaravarthy, Venkatesan T. and Pal, Arindam and Roy, Sambuddha and Sabharwal, Yogish}, title = {{Scheduling Resources for Executing a Partial Set of Jobs}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)}, pages = {199--210}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-47-7}, ISSN = {1868-8969}, year = {2012}, volume = {18}, editor = {D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.199}, URN = {urn:nbn:de:0030-drops-38598}, doi = {10.4230/LIPIcs.FSTTCS.2012.199}, annote = {Keywords: Approximation Algorithms, Partial Covering, Interval Graphs} }

Document

**Published in:** LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

In this paper we consider the problem of finding the densest subset subject to co-matroid constraints. We are given a monotone supermodular set function f defined over a universe U, and the density of a subset S is defined to be f(S)/|S|. This generalizes the concept of graph density. Co-matroid constraints are the following: given matroid M a set S is feasible, iff the complement of S is independent in the matroid. Under such constraints, the problem becomes NP-hard. The specific case of graph density has been considered in literature under specific co-matroid constraints, for example, the cardinality matroid and the partition matroid. We show a 2-approximation for finding the densest subset subject to co-matroid constraints. Thereby we improve the approximation guarantees for the result for partition matroids in the literature.

Venkatesan T. Chakaravarthy, Natwar Modani, Sivaramakrishnan R. Natarajan, Sambuddha Roy, and Yogish Sabharwal. Density Functions subject to a Co-Matroid Constraint. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 236-248, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{chakaravarthy_et_al:LIPIcs.FSTTCS.2012.236, author = {Chakaravarthy, Venkatesan T. and Modani, Natwar and Natarajan, Sivaramakrishnan R. and Roy, Sambuddha and Sabharwal, Yogish}, title = {{Density Functions subject to a Co-Matroid Constraint}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)}, pages = {236--248}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-47-7}, ISSN = {1868-8969}, year = {2012}, volume = {18}, editor = {D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.236}, URN = {urn:nbn:de:0030-drops-38627}, doi = {10.4230/LIPIcs.FSTTCS.2012.236}, annote = {Keywords: Approximation Algorithms, Submodular Functions, Graph Density} }

Document

**Published in:** LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

The maximum independent set problem (MaxIS) on general graphs is known to be NP-hard to approximate within a factor of $n^{1-epsilon}$, for any $epsilon > 0$. However, there are many ``easy" classes of graphs on which the problem can be solved in polynomial time. In this context, an interesting question is that of computing the maximum independent set in a graph that can be expressed as the union of a small number of graphs from an easy class. The MaxIS problem has been studied on unions of interval graphs and chordal graphs. We study the MaxIS problem on unions of perfect graphs (which generalize the above two classes). We present an $O(sqrt{n})$-approximation algorithm when the input graph is the
union of two perfect graphs. We also show that the MaxIS problem on unions of two comparability graphs (a subclass of perfect graphs)
cannot be approximated within any constant factor.

Venkatesan T. Chakaravarthy, Vinayaka Pandit, Sambuddha Roy, and Yogish Sabharwal. Finding Independent Sets in Unions of Perfect Graphs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 251-259, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{chakaravarthy_et_al:LIPIcs.FSTTCS.2010.251, author = {Chakaravarthy, Venkatesan T. and Pandit, Vinayaka and Roy, Sambuddha and Sabharwal, Yogish}, title = {{Finding Independent Sets in Unions of Perfect Graphs}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {251--259}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.251}, URN = {urn:nbn:de:0030-drops-28683}, doi = {10.4230/LIPIcs.FSTTCS.2010.251}, annote = {Keywords: Approximation Algorithms; Comparability Graphs; Hardness of approximation} }

Document

**Published in:** LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

We show that $S_2^psubseteq P^{prAM}$, where $S_2^p$ is the
symmetric alternation class and $prAM$ refers to the promise
version of the Arthur-Merlin class $AM$. This is derived as a
consequence of our main result that presents an $FP^{prAM}$
algorithm for finding a small set of ``collectively irrefutable
certificates'' of a given $S_2$-type matrix. The main result also
yields some new consequences of the hypothesis that $NP$ has
polynomial size circuits. It is known that the above hypothesis
implies a collapse of the polynomial time hierarchy ($PH$) to
$S_2^psubseteq ZPP^{NP}$ (Cai 2007, K"obler and Watanabe 1998).
Under the same hypothesis, we show that $PH$ collapses to
$P^{prMA}$. We also describe an $FP^{prMA}$ algorithm for learning
polynomial size circuits for $SAT$, assuming such circuits exist.
For the same problem, the previously best known result was a
$ZPP^{NP}$ algorithm (Bshouty et al. 1996).

Venkatesan T. Chakaravarthy and Sambuddha Roy. Finding Irrefutable Certificates for S_2^p via Arthur and Merlin. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 157-168, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{chakaravarthy_et_al:LIPIcs.STACS.2008.1342, author = {Chakaravarthy, Venkatesan T. and Roy, Sambuddha}, title = {{Finding Irrefutable Certificates for S\underline2^p via Arthur and Merlin}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {157--168}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1342}, URN = {urn:nbn:de:0030-drops-13421}, doi = {10.4230/LIPIcs.STACS.2008.1342}, annote = {Keywords: Symmetric alternation, promise-AM, Karp--Lipton theorem, learning circuits} }

Document

**Published in:** LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

We present a deterministic way of assigning small (log bit) weights
to the edges of a bipartite planar graph so that the minimum weight
perfect matching becomes unique. The isolation lemma as described
in (Mulmuley et al. 1987) achieves the same for general graphs
using a randomized weighting scheme, whereas we can do it
deterministically when restricted to bipartite planar graphs. As a
consequence, we reduce both decision and construction versions of
the matching problem to testing whether a matrix is singular, under
the promise that its determinant is $0$ or $1$, thus obtaining a
highly parallel SPL algorithm for bipartite planar graphs. This
improves the earlier known bounds of non-uniform SPL by (Allender
et al. 1999) and $NC^2$ by (Miller and Naor 1995, Mahajan and
Varadarajan 2000). It also rekindles the hope of obtaining a
deterministic parallel algorithm for constructing a perfect
matching in non-bipartite planar graphs, which has been open for a
long time. Our techniques are elementary and simple.

Samir Datta, Raghav Kulkarni, and Sambuddha Roy. Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 229-240, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.STACS.2008.1346, author = {Datta, Samir and Kulkarni, Raghav and Roy, Sambuddha}, title = {{Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {229--240}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1346}, URN = {urn:nbn:de:0030-drops-13465}, doi = {10.4230/LIPIcs.STACS.2008.1346}, annote = {Keywords: } }