Approximation algorithms for minimum weight partial connected set cover problem

详细信息    查看全文

• 作者：Dongyue Liang ; Zhao Zhang ; Xianliang Liu ; Wei Wang…
• 关键词：Set cover ; Greedy algorithm ; Approximation algorithm ; Submodular function
• 刊名：Journal of Combinatorial Optimization
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：31
• 期：2
• 页码：696-712
• 全文大小：469 KB
• 参考文献：Bar-Yehuda R (1999) Using homogeneous weights for approximating the partial cover problem. In: Proceeding of tenth annual ACM-SIAM symposium on discrete algorithms, pp 71–75
  Bshouty N, Burroughs L (1998) Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem. In: Proceedings of annual symposium on the theoretical aspects of computer science, pp 298–308
  Chvatal V (1979) A greedy heuristic for the set covering problem. Math Oper Res 4:233–235MathSciNet CrossRef MATH
  Elbassioni K, Jelic S, Matijevic D (2012) The relation of connected set cover and group Steiner tree. Theor Comput Sci 438:96–101MathSciNet CrossRef MATH
  Feige U (1998) A threshold of \(\ln n\) for approximating set cover. J ACM 45(4):634–652MathSciNet CrossRef MATH
  Gandhi R, Khuller S, Srinivasan A (2001) Approximation algorithms for partial covering problems. In: Proceedings of the 28th international colloquium on automata. Languages and Programming, Crete, Greece, pp 225–236
  Garg N (2005) Saving an epsilon: a 2-approximation for the \(k\) -MST problem in graphs. In: STOC, pp 396–402
  Halperin E, Srinivasan A (2002) Improved approximation algorithms for the partial vertex cover problem. In: Approximation algorithms for combinatorial optimization, pp 161–174
  Hochbaum DS (1998) The \(t\) -vertex cover problem: extending the half integrality framework with budget constraints. In: Proceedings of first international workshop on approximation algorithms for combinatorial optimization problems, pp 11–122
  Johnson DS (1974) Approximation algorithms for combinatorial problems. J Comput System Sci 9:256–278MathSciNet CrossRef MATH
  Johnson DS, Minkoff M, Phillips S (2000) The prize collecting Steiner tree problem: theorem and practice. In: SODA, pp 70–769
  Kearns MJ (1990) The computational complexity of machine learning. MIT Press, Cambridge, MA
  Khandekar R, Kortsarz G, Nutov Z (2009) Approximating fault-tolerant group steiner problem. In IARCS annual conference on FSTTCS, pp 263–274
  Khuller S, Purohit M, Sarpatwar KK (2014) Analyzing the optimasl neighborhood: algorithms for budgeted and partial connected dominating set problems. In: SODA, pp 1702–1713
  Lovasz L (1975) On the ratio of optimal integral and fractional covers. Discrete Math 13:383–390MathSciNet CrossRef MATH
  Moss A, Rabani Y (2001) Approximation algorithms for constrained node weighted Steiner tree problems. In: STOC, pp 373–382
  Shuai T, Hu X (2006) Connected set cover problem and its applications. Algorithm Aspects Inform Manag 4104:243–254CrossRef
  Slavik P (1997) Improved performance on the greedy algorithm for partial cover. Inform Process Lett 64(5):251–254MathSciNet CrossRef
  Srinivasan A (2001) Distributions on level-sets with applications to approximation algorithms. In: Proceedings of the 42nd annual IEEE symposium on foundations of computer science. Las Vegas, pp 588–597
  Wolsey LA (1982) An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4):385–393MathSciNet 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
  
• 作者单位：Dongyue Liang (1)
  Zhao Zhang (2)
  Xianliang Liu (1)
  Wei Wang (1)
  Yaolin Jiang (1) (3)
  
  1. School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an, 710049, China
  2. College of Mathematics Physics and Information Engineering, Zhejiang Normal University, Jinhua, 321004, Zhejiang, China
  3. College of Mathematics and System Sciences, Xinjiang University, Urumqi, 830046, China
  
• 刊物类别：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

文摘

In the Minimum Weight Partial Connected Set Cover problem, we are given a finite ground set \(U\), an integer \(q\le |U|\), a collection \(\mathcal {E}\) of subsets of \(U\), and a connected graph \(G_{\mathcal {E}}\) on vertex set \(\mathcal {E}\), the goal is to find a minimum weight subcollection of \(\mathcal {E}\) which covers at least \(q\) elements of \(U\) and induces a connected subgraph in \(G_{\mathcal {E}}\). In this paper, we derive a “partial cover property” for the greedy solution of the Minimum Weight Set Cover problem, based on which we present (a) for the weighted version under the assumption that any pair of sets in \(\mathcal {E}\) with nonempty intersection are adjacent in \(G_{\mathcal {E}}\) (the Minimum Weight Partial Connected Vertex Cover problem falls into this range), an approximation algorithm with performance ratio \(\rho (1+H(\gamma ))+o(1)\), and (b) for the cardinality version under the assumption that any pair of sets in \(\mathcal {E}\) with nonempty intersection are at most \(d\)-hops away from each other (the Minimum Partial Connected \(k\)-Hop Dominating Set problem falls into this range), an approximation algorithm with performance ratio \(2(1+dH(\gamma ))+o(1)\), where \(\gamma =\max \{|X|:X\in \mathcal {E}\}\), \(H(\cdot )\) is the Harmonic number, and \(\rho \) is the performance ratio for the Minimum Quota Node-Weighted Steiner Tree problem. Keywords Set cover Greedy algorithm Approximation algorithm Submodular function