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

RAIRO - Operations Research - Recherche Opérationnelle (1994)

- Volume: 28, Issue: 4, page 413-433
- ISSN: 0399-0559

## Access Full Article

top## How to cite

topPaschos, 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 28.4 (1994): 413-433. <http://eudml.org/doc/105093>.

@article{Paschos1994,

author = {Paschos, V. Th.},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {NP-complete; independent set problem; constant-ratio-polynomial-time-approximation-algorithm; set covering},

language = {eng},

number = {4},

pages = {413-433},

publisher = {EDP-Sciences},

title = {A relation between the approximated versions of minimum set covering, minimum vertex covering and maximum independent set},

url = {http://eudml.org/doc/105093},

volume = {28},

year = {1994},

}

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

PB - EDP-Sciences

VL - 28

IS - 4

SP - 413

EP - 433

LA - eng

KW - NP-complete; independent set problem; constant-ratio-polynomial-time-approximation-algorithm; set covering

UR - http://eudml.org/doc/105093

ER -

## References

top- 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. Zbl0977.68539
- 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. Zbl0459.68033MR640061
- 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. Zbl0557.90072MR807996
- 4. C. BERGE, Graphs and Hypergraphs, North Holland, Amsterdam, 1973. Zbl0254.05101MR357172
- 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. Zbl0411.68039MR519066
- 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. Zbl0786.68035MR1176675
- 8. C. LUND, M. YANNAKAKIS, On the Hardness of Approximating Minimization Problems, Proc. ACM/STOC, 1993, pp. 286-293. Zbl0814.68064MR1371491
- 9. B. MONIEN, E. SPECKENMEYER, Ramsey Numbers and an Approximation Algorithm for the Vertex Cover Problem, Acta Informatica, 1985, 22, pp. 115-123. Zbl0558.05044MR789849
- 10. C. H. PAPADIMITRIOU, K. STEIGLITZ, Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, New Jersey, 1981. Zbl0503.90060MR663728

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.