1 Search Results for "Gupta, Kanika"

Document

DOI: 10.4230/LIPIcs.FSTTCS.2014.213

Replica Placement on Directed Acyclic Graphs

Authors: Sonika Arora, Venkatesan T. Chakaravarthy, Kanika Gupta, Neelima Gupta, and Yogish Sabharwal

Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Abstract

The replica placement problem has been well studied on trees. In this paper, we study this problem on directed acyclic graphs. The replica placement problem on general DAGs generalizes the set cover problem. We present a constant factor approximation algorithm for the special case of DAGs having bounded degree and bounded tree-width (BDBT-DAGs). We also present a constant factor approximation algorithm for DAGs composed of local BDBT-DAGs connected in a tree like manner (TBDBT-DAGs). The latter class of DAGs generalizes trees as well; we improve upon the previously best known approximation ratio for the problem on trees. Our algorithms are based on the LP rounding technique; the core component of our algorithm exploits the structural properties of tree-decompositions to massage the LP solution into an integral solution.

Cite as

Sonika Arora, Venkatesan T. Chakaravarthy, Kanika Gupta, Neelima Gupta, and Yogish Sabharwal. Replica Placement on Directed Acyclic Graphs. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 213-225, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{arora_et_al:LIPIcs.FSTTCS.2014.213,
  author =	{Arora, Sonika and Chakaravarthy, Venkatesan T. and Gupta, Kanika and Gupta, Neelima and Sabharwal, Yogish},
  title =	{{Replica Placement on Directed Acyclic Graphs}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{213--225},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Raman, Venkatesh and Suresh, S. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.213},
  URN =		{urn:nbn:de:0030-drops-48449},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.213},
  annote =	{Keywords: Approximation Algorithms, LP Rounding}
}

Refine by Author
1 Arora, Sonika
1 Chakaravarthy, Venkatesan T.
1 Gupta, Kanika
1 Gupta, Neelima
1 Sabharwal, Yogish

Refine by Classification

Refine by Keyword
1 Approximation Algorithms
1 LP Rounding

Refine by Type
1 document

Refine by Publication Year
1 2014

1 Search Results for "Gupta, Kanika"

Replica Placement on Directed Acyclic Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message