A New Approximation Algorithm for k-Set Cover Problem

详细信息    查看全文

• 作者：Hanaa A. E. Essa ; Yasser M. Abd El-Latif…
• 关键词：Set cover problem (SCP) ; An approximation algorithm ; A greedy algorithm ; An NP ; complete optimization problem
• 刊名：Arabian Journal for Science and Engineering
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：41
• 期：3
• 页码：935-940
• 全文大小：779 KB
• 参考文献：1.Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E.; Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New-York (1972)
  2.Housos E., Elmoth T.: Automatic optimization of subproblems in scheduling airlines crews. Interfaces. 27, 68–77 (1997)CrossRef
  3.Lourenço H.R., Portugal P., Paixão J.P.: Multiobjective metaheuristics for the bus-driver scheduling problem. Transp. Sci. 35, 331–343 (2001)CrossRef MATH
  4.Chvátal V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4, 233–235 (1979)CrossRef MathSciNet MATH
  5.Lovász L.: On the ratio of optimal integral and fractional covers. Discrete Math. 13, 383–390 (1975)CrossRef MathSciNet MATH
  6.Slavík P.: A tight analysis of the greedy algorithm for set cover. J. Algorithms. 25, 237–254 (1997)CrossRef MathSciNet MATH
  7.Feige U.: A threshold of ln n for approximating set cover. J. ACM. 45, 634–652 (1998)CrossRef MathSciNet MATH
  8.Raz, R.; Safra, S.: A sub-constant error probability low-degree test, and sub-constant error-probability PCP characterization of NP. Proc. STOC 1997, pp. 475–484 (1997)
  9.Goldschmidt O., Hochbaum D.S., Yu G.: A modified greedy heuristic for the set covering problem with improved worst case bound. Inf. Process. Lett. 48, 305–310 (1993)CrossRef MathSciNet MATH
  10.Halldórsson, M.M.: Approximating k set cover and complementary graph coloring. In: Proc. 5th Conference on Integer Programming and Combinatorial Optimization, IPCO’1996, pp. 118–131 (1996)
  11.Duh, R.; Fürer, M.: Approximation of k-set cover by semi local Optimization. Proc. STOC 1997, pp. 256–264 (1997)
  12.Levin, A.: Approximating the Un-weighted k-Set Cover Problem, Greedy Meets Local Search. WAOA LNCS 4368, pp. 290–301 (2006)
  13.Athanassopoulos, S.; Caragiannis, I.; Kaklamanis, C.: Analysis of approximation algorithms for k-set cover using factor-revealing linear Programs. Theory of Computing Systems, in press, 45, 555–576 (2009). doi:10.​1007/​s00224-008-9112-3 .
  
• 作者单位：Hanaa A. E. Essa (1)
  Yasser M. Abd El-Latif (2)
  Salwa M. Ali (2)
  Soheir M. Khamis (2)
  
  1. Department of Math., Faculty of Science, Tanta University, Tanta, Egypt
  2. Division of Computer Science, Department of Math., Faculty of Science, Ain Shams University, Cairo, Egypt
  
• 刊物类别：Engineering
• 刊物主题：Engineering, general
  Mathematics
  Science, general
  
• 出版者：Springer Berlin / Heidelberg

文摘

In the set cover problem (SCP), a set of elements \({X = \{x_{1}, x_{2}, \ldots, x_{n}\}}\) and a collection \({F = \{S_{1}, S_{2}, \ldots, S_{m}\}}\) of subsets of X, for some integers \({n, m \geq 1}\), are given. In addition, each element of \({X}\) belongs to at least one member of F. The problem is to find a sub-collection \({C \subseteq F}\) such that \({\bigcup\nolimits_{S\in C} S = X}\) and C has the minimum cardinality. When \({|S| \leq k}\) for all \({S \in F}\), the k-set cover problem (k-SCP) is obtained. For all \({k \geq 3}\), the k-SCP is an NP-complete optimization problem (Karp in Complexity of computer computations. Plenum Press, New-York, pp 85–103, 1972). It is well known that a greedy algorithm for the k-SCP is a \({h_{k}}\)-approximation algorithm, where \({h_{k} = \sum\nolimits_{i=1}^k {\frac{1}{i}}}\) is the \({k^{th}}\) harmonic number. Since the SCP is a fundamental problem, so there is a research effort to improve this approximation ratio. In this paper, the authors propose an approximation algorithm which accepts any instance of the k-SCP problem as an input. This approximation algorithm is a \({(1 + \frac{1}{k})}\)-algorithm with a polynomial running time for \({k \geq 6}\) that improves the previous best approximation ratio \({h_{k} - 0.5902}\) for all values of \({k \geq 6}\).