2-приближённый алгоритм для задачи о вершинном покрытии через максимальное по включению паросочетание, 2-приближение для взвешенного случая через линейное программирование. Жадный \( \log n \)-приближённый алгоритм для задачи о покрытии множествами. \( \log n \)-приближённый алгоритм для задачи о множестве представителей через линейное программирование и вероятностное округление.