THE APPROXIMABILITY BEHAVIOR OF SOME COMB INATORIAL PROBLEMS WITH RESPECT TO THE APPROXIMABILITY OF A CLASS OF MAXIMUM INDEPENDENT SET PROBLEMS

Authors
DEMANGE M PASCHOS VT
Citation
M. Demange et Vt. Paschos, THE APPROXIMABILITY BEHAVIOR OF SOME COMB INATORIAL PROBLEMS WITH RESPECT TO THE APPROXIMABILITY OF A CLASS OF MAXIMUM INDEPENDENT SET PROBLEMS, Comptes rendus de l'Academie des sciences. Serie 1, Mathematique, 321(5), 1995, pp. 645-648
Citations number
3
Categorie Soggetti
Mathematics, General",Mathematics
Journal title
Comptes rendus de l'Academie des sciences. Serie 1, Mathematique → ACNP
ISSN journal
07644442
Volume
321
Issue
5
Year of publication
1995
Pages
645 - 648
Database
ISI
SICI code
0764-4442(1995)321:5<645:TABOSC>2.0.ZU;2-K
Abstract
We introduce a class maximum independent set problems and we give some conditional results that, leaving from positive or negative hypothese s on the approximability behaviour of this class, provide approximatio n results for minimum vertex covering problem and a problem of convex programming including quadratic programming.