Approximation of independent sets in graphs (Q4400840)

This paper is an introduction to the performance ratios of a selection of independent set approximation algorithms. From the author's introduction: The primary criteria for selection was (sic) simplicity of the algorithm and the proof. We state some observations that have not formally appeared before, give some recent results, and present simpler proofs of other results. \dots{} We present a number of particular results illustrating particular algorithmic strategies: subgraph removal, semi-definite programming, partitioning, greedy algorithms, and local search. We give a listing of known performance results, and finish with a discussion of open issues. For the entire collection see [Zbl 0892.00051].