THE RAMSEY ALGORITHM

This algorithm improved the best bounds known for approximating the independent set and graph coloring problems and prove that the approaches used to date to obtain such results can not be improved much further. I start with the Ramsey algorithm for finding independent sets in graphs, which is actually a schema of algorithms parameterized by the pivoting function applied, similar to the greedy algorithm. It has the property that its solution on any graph is at least as large as the one the corresponding greedy algorithm finds. The algorithm Ramsey is related to a classical problem in extremal graph theory [1].