Approximation algorithms for integer covering problems via greedy column generation
RAIRO - Operations Research - Recherche Opérationnelle (1994)
- Volume: 28, Issue: 3, page 283-302
- ISSN: 0399-0559
Access Full Article
topHow to cite
topReferences
top- 1. V. CHVÁTAL, A greedy heuristic for the set-covering problem, Mathematics of Operations Research, 1979, 4, p. 233-235. Zbl0443.90066MR539404
- 2. V. CHVÁTAL, Linear Programming, Freeman, New York, 1983. Zbl0537.90067MR717219
- 3. H. DYCKHOFF, A typology of cutting and packing problems, European Journal of Operational Research, 1990, 44, p. 145-159. Zbl0684.90076MR1036150
- 4. G. DOBSON, Worst-case analysis of greedy heuristics for integer programming with nonnegative data, Mathematics of Operations Research, 1982, 7, p. 515-531. Zbl0498.90061MR686528
- 5. P. C. GILMORE, R. E. GOMORY, A linear programming approach to the cutting stock problem, Operations Research, 1963, 9, p. 849-859. Zbl0096.35501MR137589
- 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. Zbl0929.90071
- 7. R. W. HAESSLER, P. E. SWEENEY, Cutting stock problems and solution procedures, European Journal of Operational Research, 1991, 54, p. 141-150. Zbl0736.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. Zbl0800.68864
- 9. D. S. JOHNSON, Approximation algorithms for combinatorial problems, Journal of Computer and System Sciences, 1974, 9, p. 256-278. Zbl0296.65036MR449012
- 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. Zbl0308.05109MR389644
- 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. Zbl0878.68034
- 12. L. LOVÁSZ, On the ratio of optimal integral and fractional covers, Discrete Mathematics, 1974, 13, p. 383-390. Zbl0323.05127MR384578
- 13. C. LUND, M. YANNAKAKIS, On the hardness of approximating minimization problems, Working Paper AT&T Bell Labs, NJ, 1992. Zbl0814.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. Zbl0644.90061MR897292
- 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. Zbl0944.90001MR948455
- 16. N. J. NILSSON, Probabilistic logic, Artificial Intelligence, 1986, 28, p. 71-87. Zbl0589.03007MR832294
- 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. Zbl0699.68077MR1039300