Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs. (English) Zbl 1170.90461
Summary: We present new combinatorial approximation algorithms for the \(k\)-set cover problem. Previous approaches are based on extending the greedy algorithm by efficiently handling small sets. The new algorithms further extend these approaches by utilizing the natural idea of computing large packings of elements into sets of large size. Our results improve the previously best approximation bounds for the \(k\)-set cover problem for all values of \(k\geq 6\). The analysis technique used could be of independent interest; the upper bound on the approximation factor is obtained by bounding the objective value of a \(factor-revealing\) linear program.
References:
| [1] | Chvátal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4, 233–235 (1979) · Zbl 0443.90066 · doi:10.1287/moor.4.3.233 |
| [2] | Duh, R., Fürer, M.: Approximation of k-set cover by semi local optimization. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC ’97), pp. 256–264 (1997) · Zbl 0962.68172 |
| [3] | Feige, U.: A threshold of lnn for approximating set cover. J. ACM 45(4), 634–652 (1998) · Zbl 1065.68573 · doi:10.1145/285055.285059 |
| [4] | Goldschmidt, O., Hochbaum, D., Yu, G.: A modified greedy heuristic for the set covering problem with improved worst case bound. Inf. Process. Lett. 48, 305–310 (1993) · Zbl 0811.68099 · doi:10.1016/0020-0190(93)90173-7 |
| [5] | Halldórsson, M.M.: Approximating discrete collections via local improvements. In: Proceedings of the 6th Annual ACM/SIAM Symposium on Discrete Algorithms (SODA ’95), pp. 160–169 (1995) · Zbl 0847.90136 |
| [6] | Halldórsson, M.M.: Approximating k-set cover and complementary graph coloring. In: Proceedings of the 5th Conference on Integer Programming and Combinatorial Optimization (IPCO ’96). LNCS, vol. 1084, pp. 118–131. Springer, Berlin (1996) |
| [7] | Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating k-set packing. Comput. Complex. 15(1), 20–39 (2006) · Zbl 1103.90105 · doi:10.1007/s00037-006-0205-6 |
| [8] | Hurkens, C.A.J., Schrijver, A.: On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discrete Math. 2(1), 68–72 (1989) · Zbl 0733.05003 · doi:10.1137/0402008 |
| [9] | Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50(6), 795–824 (2003) · Zbl 1325.90060 · doi:10.1145/950620.950621 |
| [10] | Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9, 256–278 (1974) · Zbl 0296.65036 · doi:10.1016/S0022-0000(74)80044-9 |
| [11] | Kann, V.: Maximum bounded 3-dimensional matching is MAX SNP-complete. Inf. Process. Lett. 37, 27–35 (1991) · Zbl 0711.68045 · doi:10.1016/0020-0190(91)90246-E |
| [12] | Levin, A.: Approximating the unweighted k-set cover problem: greedy meets local search. In: Proceedings of the 4th International Workshop on Approximation and Online Algorithms (WAOA ’06). LNCS, vol. 4368, pp. 290–310. Springer, Berlin (2006) · Zbl 1129.68588 |
| [13] | Lovász, L.: On the ratio of optimal integral and fractional covers. Discrete Math. 13, 383–390 (1975) · Zbl 0323.05127 · doi:10.1016/0012-365X(75)90058-8 |
| [14] | Slavík, P.: A tight analysis of the greedy algorithm for set cover. J. Algorithms 25, 237–254 (1997) · Zbl 0887.68040 · doi:10.1006/jagm.1997.0887 |
| [15] | Trevisan, L.: Non-approximability results for optimization problems on bounded degree instances. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC ’01), pp. 453–461 (2001) · Zbl 1323.90059 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
