Approximation algorithms for integer covering problems via greedy column generation
RAIRO - Operations Research - Recherche Opérationnelle, Volume 28 (1994) no. 3, p. 283-302
@article{RO_1994__28_3_283_0,
author = {Crama, Y. and Van De Klundert, J.},
title = {Approximation algorithms for integer covering problems via greedy column generation},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
publisher = {EDP-Sciences},
volume = {28},
number = {3},
year = {1994},
pages = {283-302},
zbl = {0830.90107},
mrnumber = {1290532},
language = {en},
url = {http://www.numdam.org/item/RO_1994__28_3_283_0}
}

Crama, Y.; Van De Klundert, J. Approximation algorithms for integer covering problems via greedy column generation. RAIRO - Operations Research - Recherche Opérationnelle, Volume 28 (1994) no. 3, pp. 283-302. http://www.numdam.org/item/RO_1994__28_3_283_0/

1. V. Chvátal, A greedy heuristic for the set-covering problem, Mathematics of Operations Research, 1979, 4, p. 233-235. | MR 539404 | Zbl 0443.90066

2. V. Chvátal, Linear Programming, Freeman, New York, 1983. | MR 717219 | Zbl 0537.90067

3. H. Dyckhoff, A typology of cutting and packing problems, European Journal of Operational Research, 1990, 44, p. 145-159. | MR 1036150 | Zbl 0684.90076

4. G. Dobson, Worst-case analysis of greedy heuristics for integer programming with nonnegative data, Mathematics of Operations Research, 1982, 7, p. 515-531. | MR 686528 | Zbl 0498.90061

5. P. C. Gilmore, R. E. Gomory, A linear programming approach to the cutting stock problem, Operations Research, 1963, 9, p. 849-859. | MR 137589 | Zbl 0096.35501

6. M. X. Goemans, D. P. Williamson, new 3/4-approximation algorithm for MAX SAT, In Proc. of the third IPCO Conference, G. RINALDI and L. WOLSEY eds., 1993, p. 313-321. | Zbl 0929.90071

7. R. W. Haessler, P. E. Sweeney, Cutting stock problems and solution procedures, European Journal of Operational Research, 1991, 54, p. 141-150. | Zbl 0736.90062

8. P. Hansen, B. Jaumard, M. Poggi De Aragão, Column generation methods for probabilistic logic, ORSA Journal on Computing, 1991, 3, p. 135-148. | Zbl 0800.68864

9. D. S. Johnson, Approximation algorithms for combinatorial problems, Journal of Computer and System Sciences, 1974, 9, p. 256-278. | MR 449012 | Zbl 0296.65036

10. D. S. Johnson, Worst-case behavior of graph coloring algorithms, In Proc. 5th Southeastern Conf. on Combinatorics, Graph Theory and Computing, p. 513-527. Utilitas Mathematica Publ. Winnipeg, Ontario, 1974 b. | MR 389644 | Zbl 0308.05109

11. D. Kavvadias, C. P. Papadimitriou, A linear programming approach to reasoning about probabilities, Annals of Mathematics and Artificial Intelligence, 1990, 1, p. 189-205. | Zbl 0878.68034

12. L. Lovász, On the ratio of optimal integral and fractional covers, Discrete Mathematics, 1974, 13, p. 383-390. | MR 384578 | Zbl 0323.05127

13. C. Lund, M. Yannakakis, On the hardness of approximating minimization problems, Working Paper AT&T Bell Labs, NJ, 1992. | Zbl 0814.68064

14. M. Minoux, A class of combinatorial problems with polynomially solvable large scale set covering/partioning relaxations, R.A.I.R.O. Recherche opérationnelle/Operations Research, 1987, 21, p. 105-136. | Numdam | MR 897292 | Zbl 0644.90061

15. G. M. Nemhauser, L. A. Wolsey, Integer and Combinatorial Optimization, Wiley- Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, New York Chichester Brisbane Toronto Singapore, 1988. | MR 948455 | Zbl 0944.90001

16. N. J. Nilsson, Probabilistic logic, Artificial Intelligence, 1986, 28, p. 71-87. | MR 832294 | Zbl 0589.03007

17. H. U. Simon, The analysis of dynamic and hybrid channel assignment, Working Paper, Universität des Saarlandes, Saarbrücken, 1988.

18. H. U. Simon, On approximate solutions for combinatorial optimization problems, SIAM Journal on Discrete Mathematics, 1990, 3, p. 294-310. | MR 1039300 | Zbl 0699.68077