Editing Clique problem (section)

===Approximation algorithms===
Several authors have considered [[approximation algorithm]]s that attempt to find a clique or independent set that, although not maximum, has size as close to the maximum as can be found in polynomial time. Although much of this work has focused on independent sets in sparse graphs, a case that does not make sense for the complementary clique problem, there has also been work on approximation algorithms that do not use such sparsity assumptions.<ref>{{harvtxt|Boppana|Halldórsson|1992}}; {{harvtxt|Feige|2004}}; {{harvtxt|Halldórsson|2000}}.</ref>

{{harvtxt|Feige|2004}} describes a polynomial time algorithm that finds a clique of size {{math|Ω((log&nbsp;''n''/log&nbsp;log&nbsp;''n'')<sup>2</sup>)}} in any graph that has clique number {{math|Ω(''n''/log<sup>''k''</sup>''n'')}} for any constant {{mvar|k}}. By using this algorithm when the clique number of a given input graph is between {{math|''n''/log&nbsp;''n''}} and {{math|''n''/log<sup>3</sup>''n''}}, switching to a different algorithm of {{harvtxt|Boppana|Halldórsson|1992}} for graphs with higher clique numbers, and choosing a two-vertex clique if both algorithms fail to find anything, [[Uriel Feige|Feige]] provides an approximation algorithm that finds a clique with a number of vertices within a factor of {{math|O(''n''(log&nbsp;log&nbsp;''n'')<sup>2</sup>/log<sup>3</sup>''n'')}} of the maximum. Although the [[approximation ratio]] of this algorithm is weak, it is the best known to date.<ref>{{harvtxt|Liu|Lu|Yang|Xiao|2015}}: "In terms of the number of vertices in graphs, Feige shows the currently known best approximation ratio". Liu et al. are writing about the [[maximum independent set]] but for purposes of approximation there is no difference between the two problems.</ref> The results on [[hardness of approximation]] described below suggest that there can be no approximation algorithm with an approximation ratio significantly less than linear.