文章基本信息

标题：Replica Placement on Directed Acyclic Graphs
本地全文：下载
作者：Sonika Arora ; Venkatesan T. Chakaravarthy ; Kanika Gupta 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：29
页码：213-225
DOI：10.4230/LIPIcs.FSTTCS.2014.213
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Approximation Algorithms; LP Rounding