A relation between the approximated versions of minimum set covering, minimum vertex covering and maximum independent set

Paschos, V. Th.

Paschos, V. Th.

RAIRO - Operations Research - Recherche Opérationnelle, Tome 28 (1994) no. 4, pp. 413-433.

MR Zbl

@article{RO_1994__28_4_413_0,
     author = {Paschos, V. Th.},
     title = {A relation between the approximated versions of minimum set covering, minimum vertex covering and maximum independent set},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {413--433},
     publisher = {EDP-Sciences},
     volume = {28},
     number = {4},
     year = {1994},
     mrnumber = {1304252},
     zbl = {0857.90130},
     language = {en},
     url = {http://www.numdam.org/item/RO_1994__28_4_413_0/}
}

TY  - JOUR
AU  - Paschos, V. Th.
TI  - A relation between the approximated versions of minimum set covering, minimum vertex covering and maximum independent set
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 1994
SP  - 413
EP  - 433
VL  - 28
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/RO_1994__28_4_413_0/
LA  - en
ID  - RO_1994__28_4_413_0
ER  -

%0 Journal Article
%A Paschos, V. Th.
%T A relation between the approximated versions of minimum set covering, minimum vertex covering and maximum independent set
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 1994
%P 413-433
%V 28
%N 4
%I EDP-Sciences
%U http://www.numdam.org/item/RO_1994__28_4_413_0/
%G en
%F RO_1994__28_4_413_0

Paschos, V. Th. A relation between the approximated versions of minimum set covering, minimum vertex covering and maximum independent set. RAIRO - Operations Research - Recherche Opérationnelle, Tome 28 (1994) no. 4, pp. 413-433. http://www.numdam.org/item/RO_1994__28_4_413_0/

Bibliographie
Cité par

1. S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof Verification and Intractability of Approximation Problems, Proc. IEEE/FOCS, 1992, pp. 14-23. | Zbl

2. R. Bar-Yehuda, S. Even, A Linear Time Approximation Algorithm for the Weighted Vertex Cover Problem, J. of Algorithms, 1981, 2, pp. 198-203. | MR | Zbl

3. R. Bar-Yehuda, S. Even, A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem, Annals of Discr. Appl. Maths, 1985, 25, pp. 27-46. | MR | Zbl

4. C. Berge, Graphs and Hypergraphs, North Holland, Amsterdam, 1973. | MR | Zbl

5. M. R. Garey, D. S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, San Francisco, 1979. | MR | Zbl

6. F. Gavril, cited in [5], p. 134.

7. D. S. Johnson, The NP-Completeness Column: On Ongoing Guide, J. of Algorithms, 1992, 13, pp. 502-524. | MR | Zbl

8. C. Lund, M. Yannakakis, On the Hardness of Approximating Minimization Problems, Proc. ACM/STOC, 1993, pp. 286-293. | MR | Zbl

9. B. Monien, E. Speckenmeyer, Ramsey Numbers and an Approximation Algorithm for the Vertex Cover Problem, Acta Informatica, 1985, 22, pp. 115-123. | MR | Zbl

10. C. H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, New Jersey, 1981. | MR | Zbl