На странице википедии приведен пример аппроксимации 3/2, в котором представлен жадный алгоритм для задачи с заданным покрытием.
Мы можем видеть две группы множеств, составляющих F. 2 комплекта («линии»), образующие разбиение, каждый из которых имеет половину «точек». И 3 других набора («прямоугольники»), образующих другой раздел, с соотв. 2, 4 и 8 баллов.
Жадный алгоритм будет выбирать «прямоугольники», поскольку он начинается с наибольшего набора F.
Эту схему можно адаптировать для «худшего» приближения, чтобы «обмануть» жадный алгоритм.
Рецепт: нарисуйте ту же фигуру, но с сеткой 31 x 2 вместо 7 x 2. Сохраните две линии с половиной точек в каждой (по-прежнему образуя разделение) и добавьте два «прямоугольника» (два самых больших, они будет иметь соответственно 16 и 32 «точки») на правой стороне.
Жадный алгоритм вернет 5 «прямоугольников», в то время как оптимальное решение будет состоять из двух линий, поэтому приближение составляет 5/2 > 2.
Обратите внимание, что этот процесс можно расширять бесконечно (с сеткой (2^n)-1 per 2), поэтому вы можете доказать, что жадный алгоритм для покрытия набора не является k -приближением для любого числа k.