Geodesic
A Note on the Improvement of the Maximum Independent Set's Approximation Ratio
Yugoslav journal of operations research, Tome 5 (1995) no. 1, p. 21 .

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

We present an $O(n^{3.5})$ approximation algorithm for maximum independent set problem achieving, in unweighted case, a worst case approximation ratio strictly greater than $(2 / \Delta )$, for a graph of order n and maximum vertex degree $\Delta$. The best known ratio was, up to now, equal to $2 / \Delta$ and its improvement is considered as an interesting open problem.
Keywords: Approximation algorithms, analysis of algorithms, combinatorial problems, independent set, computational complexity 
@article{YJOR_1995_5_1_a1,
     author = {Vangelis Th. Paschos},
     title = {A {Note} on the {Improvement} of the {Maximum} {Independent} {Set's} {Approximation} {Ratio}},
     journal = {Yugoslav journal of operations research},
     pages = {21 },
     publisher = {mathdoc},
     volume = {5},
     number = {1},
     year = {1995},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_1995_5_1_a1/}
}
TY  - JOUR
AU  - Vangelis Th. Paschos
TI  - A Note on the Improvement of the Maximum Independent Set's Approximation Ratio
JO  - Yugoslav journal of operations research
PY  - 1995
SP  - 21 
VL  - 5
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/YJOR_1995_5_1_a1/
LA  - en
ID  - YJOR_1995_5_1_a1
ER  - 
%0 Journal Article
%A Vangelis Th. Paschos
%T A Note on the Improvement of the Maximum Independent Set's Approximation Ratio
%J Yugoslav journal of operations research
%D 1995
%P 21 
%V 5
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/YJOR_1995_5_1_a1/
%G en
%F YJOR_1995_5_1_a1
Vangelis Th. Paschos. A Note on the Improvement of the Maximum Independent Set's Approximation Ratio. Yugoslav journal of operations research, Tome 5 (1995) no. 1, p. 21 . http://geodesic.mathdoc.fr/item/YJOR_1995_5_1_a1/