@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://archive.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://archive.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://archive.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, Volume 28 (1994) no. 4, pp. 413-433. http://archive.numdam.org/item/RO_1994__28_4_413_0/
1. Proof Verification and Intractability of Approximation Problems, Proc. IEEE/FOCS, 1992, pp. 14-23. | Zbl
, , , , ,2. A Linear Time Approximation Algorithm for the Weighted Vertex Cover Problem, J. of Algorithms, 1981, 2, pp. 198-203. | MR | Zbl
, ,3. A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem, Annals of Discr. Appl. Maths, 1985, 25, pp. 27-46. | MR | Zbl
, ,4. Graphs and Hypergraphs, North Holland, Amsterdam, 1973. | MR | Zbl
,5. Computers and Intractability. A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, San Francisco, 1979. | MR | Zbl
, ,6. cited in [5], p. 134.
,7. The NP-Completeness Column: On Ongoing Guide, J. of Algorithms, 1992, 13, pp. 502-524. | MR | Zbl
,8. On the Hardness of Approximating Minimization Problems, Proc. ACM/STOC, 1993, pp. 286-293. | MR | Zbl
, ,9. Ramsey Numbers and an Approximation Algorithm for the Vertex Cover Problem, Acta Informatica, 1985, 22, pp. 115-123. | MR | Zbl
, ,10. Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, New Jersey, 1981. | MR | Zbl
, ,