A note on the improvement of the maximum independent sets approximation ratio

0.00 Avg rating—0 Votes

Article ID:	iaor1997248
Country:	Serbia
Volume:	5
Start Page Number:	21
End Page Number:	26
Publication Date:	Dec 1995
Journal:	Yugoslav Journal of Operations Research
Authors:	Paschos Vangelis T.H.
Keywords:	combinatorial analysis, sets

Abstract:

The paper presents an O(n³’.⁵) approximation algorithm for the maximum independent set problem achieving, in unweighted case, a worst case approximation ratio strictly greater than (2/ℝ), for a graph of order n and maximum vertex degree ℝ. The best known ratio was, up to now, equal to 2/ℝ and its improvement is considered as an interesting open problem.

Reviews

Required fields are marked *. Your email address will not be published.