Several authors have considered approximation algorithms 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.
Mai mulți autori au considerat algoritmi de aproximare care încearcă să găsească o clică sau o mulțime independentă care, deși nu este maximă, are dimensiuni cât mai aproape de maxim, în timp polinomial.