LIPIcs.FSTTCS.2014.213.pdf
- Filesize: 0.89 MB
- 13 pages
Document
Replica Placement on Directed Acyclic Graphs
Authors
-
Part of:
Volume:
34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2014-12-12
Cite As Get BibTex
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)
https://doi.org/10.4230/LIPIcs.FSTTCS.2014.213
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.
Subject Classification
Keywords
- Approximation Algorithms
- LP Rounding
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
S. Arora, V. T. Chakaravarthy, N. Gupta, K. Mukherjee, and Y. Sabharwal. Replica placement via capacitated vertex cover. FSTTCS, 2013.
-
A. Benoit, H. Larchevêque, and P. Renaud-Goud. Optimal algorithms and approximation algorithms for replica placement with distance constraints in tree networks. In IPDPS, pages 1022-1033, 2012.
-
A. Benoit, V. Rehn-Sonigo, and Y. Robert. Replica placement and access policies in tree networks. IEEE Trans. on Parallel and Dist. Systems, 19:1614-1627, 2008.
-
J. Chuzhoy and J. Naor. Covering problems with hard capacities. SIAM Journal Computing, 36(2):498-515, 2006.
-
I. Cidon, S. Kutten, and R. Soffer. Optimal allocation of electronic content. Computer Networks, 40:205-218, 2002.
-
U. Feige. A threshold of ln n for approximating set cover. JACM, 45(4):634-652, 1998.
-
R. Gandhi, E. Halperin, S. Khuller, G. Kortsarz, and A. Srinivasan. An improved approximation algorithm for vertex cover with hard capacities. JCSS, 72(1), 2006.
-
K. Kalpakis, K. Dasgupta, and O. Wolfson. Optimal placement of replicas in trees with read, write, and storage costs. IEEE Trans. on Parallel and Dist. Sys., 12:628-637, 2001.
-
M. J. Kao and C. S. Liao. Capacitated domination problem. Algorithmica, pages 1-27, 2009.
-
Y. F. Lin, P. Liu, and J. J. Wu. Optimal placement of replicas in data grid environments with locality assurance. In ICPADS, 2006.
-
B. Saha and S. Khuller. Set cover revisited: Hypergraph cover with hard capacities. In ICALP, 2012.
-
L. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385-393, 1982.
-
J. J. Wu, Y. F. Lin, and P. Liu. Optimal replica placement in hierarchical data grids with locality assurance. J. of Parallel and Dist. Computing, 68:1517-1538, 2008.