An approximation algorithm for maximum weight budgeted connected set cover

详细信息    查看全文

• 作者：Yingli Ran ; Zhao Zhang ; Ker-I Ko ; Jun Liang
• 关键词：Budgeted set cover ; Connected set cover ; Approximation algorithm
• 刊名：Journal of Combinatorial Optimization
• 出版年：2016
• 出版时间：May 2016
• 年：2016
• 卷：31
• 期：4
• 页码：1505-1517
• 全文大小：482 KB
• 参考文献：Avrachenkov K, Basu P, Neglia G, Ribeiro BF, Towsley D (2014) Pay few, influence most: online myopic network covering, NetSciCom’14, INFOCOM WKSHPS, Toronto, ON, pp. 813–818
  Bateni M, Hajiaghayi M, Liaghat V (2013) Improved approximation algorithms for (budgeted) node-weighted steiner problems. ICALP’13, LNCS 7965, pp. 81–92
  Du D-Z, Ko K-I, Hu X (2011) Design and analysis of approximation algorithms. Springer, New York
  Guha S, Moss A, Naor J, Schieber B (1999) Efficient recovery from power outage, STOC’99, Atlanta, UAS, pp. 574–582
  Khuller S, Moss A, Naor J (1999) The budgeted maximum coverage problem. Inf Process Lett 70:39–45MathSciNet CrossRef MATH
  Khuller S, Purohit M, Sarpatwar KK (2014) Analyzing the optimal neighborhood: algorithms for the budgeted and partial connected dominating set prooblem. SODA’14, pp. 1702–1713
  Moss A, Rabani Y (2007) Approximation algorithms for constrained node weighted Steiner tree problems. SIAM J Comput 37:460–481MathSciNet CrossRef MATH
  Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions-I. Math Program 14:265–294MathSciNet CrossRef MATH
  Wu W, Du H, Jia X, Li Y, Huang S (2006) Minimum connected dominating sets and maximal independent sets in unit disk graphs. Theor Comput Sci 352:1–7MathSciNet CrossRef MATH
  Zhang Z, Gao X, Wu W (2009) Algorithms for connected set cover problem and fault-tolerant connected set cover problem. Theor Comput Sci 410:812–817MathSciNet CrossRef MATH
  
• 作者单位：Yingli Ran (1)
  Zhao Zhang (2)
  Ker-I Ko (3)
  Jun Liang (4)
  
  1. College of Mathematics and System Sciences, Xinjiang University, Urumqi, 830046, Xinjiang, China
  2. College of Mathematics Physics and Information Engineering, Zhejiang Normal University, Jinhua, 321004, Zhejiang, China
  3. Department of Computer Science, National Chiao Tung University, Hsinchu, 30050, Taiwan
  4. Department of Computer Science, University of Texas at Dallas, Richardson, TX, 75080, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

This paper studies approximation algorithm for the maximum weight budgeted connected set cover (MWBCSC) problem. Given an element set \(X\), a collection of sets \({\mathcal {S}}\subseteq 2^X\), a weight function \(w\) on \(X\), a cost function \(c\) on \({\mathcal {S}}\), a connected graph \(G_{\mathcal {S}}\) (called communication graph) on vertex set \({\mathcal {S}}\), and a budget \(L\), the MWBCSC problem is to select a subcollection \({\mathcal {S'}}\subseteq {\mathcal {S}}\) such that the cost \(c({\mathcal {S'}})=\sum _{S\in {\mathcal {S'}}}c(S)\le L\), the subgraph of \(G_{\mathcal {S}}\) induced by \({\mathcal {S'}}\) is connected, and the total weight of elements covered by \({\mathcal {S'}}\) (that is \(\sum _{x\in \bigcup _{S\in {\mathcal {S'}}}S}w(x)\)) is maximized. We present a polynomial time algorithm for this problem with a natural communication graph that has performance ratio \(O((\delta +1)\log n)\), where \(\delta \) is the maximum degree of graph \(G_{\mathcal {S}}\) and \(n\) is the number of sets in \({\mathcal {S}}\). In particular, if every set has cost at most \(L/2\), the performance ratio can be improved to \(O(\log n)\).