Контрпример (простой, показывает, что жадный не всегда оптимален). Пусть $U=\{a,b,c\}$ и коллекция множеств с весами:
- $S_1=\{a,b\},w(S_1)=3$ - $S_2=\{b,c\},w(S_2)=3$ - $S_3=\{a,b,c\},w(S_3)=5$
Жадный алгоритм по правилу «минимальный стоимость/новые\ элементы» сначала сравнивает:
$\frac{w(S_1)}{|S_1|}=3/2=1.5,\frac{w(S_2)}{|S_2|}=1.5,\frac{w(S_3)}{|S_3|}=5/3\approx 1.667$.
Он выберет, скажем, $S_1$, затем потребуется покрыть $c$ — выбор $S_2$ даёт итоговую стоимость $3+3=6$. Но оптимум — взять $S_3$ с весом $5$. Итого жадный дал решение хуже оптимального (отношение $6/5$).
Анализ аппроксимационной границы. Для задачи покрытия множества жадный алгоритм даёт приближение
$H_n=1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}\approx \ln n$,
где $n=|U|$. Короткая доказательная идея (неформально):
- Пусть оптимум требует $k$ множеств (или имеет стоимость $OPT$ в весовом варианте). В любой текущей непокрытой части остаётся не более $r$ элементов; среди множеств оптимума есть одно, покрывающее как минимум $r/k$ оставшихся элементов. Значит жадный шаг покрывает ≥$r/k$ элементов, и последовательное суммирование даёт, что число выбранных множеств ≤ $k\cdot H_n$. В весовом варианте аналогично через зарядное рассуждение или двойственную оценку получается $Cos{t}_{greedy}\le OPT\cdot H_n$.
Этот предел асимптотически точен: существуют семейства, где отношение жадного к оптимальному достигает $\Theta (\ln n)$. Также известно, что улучшить фактор $\ln n$ полиномиальным алгоритмом в общем случае нельзя (кроме очень малых фактов), т.е. логарифмическая граница почти тайтна.
Улучшения и альтернативы
- Предобработка: удалить доминируемые множества и элементы с одинаковыми покрытиями; это часто улучшает практику.
- Локальный поиск (k-exchange): начать с решения (например, жадного) и пытаться улучшать заменой ≤$k$ множеств на ≤$k-1$ — даёт практический выигрыш, при больших $k$ может найти близкие к оптимуму решения.
- LP-релаксация и округление: решить LP
$\min \sum _{S}w(S)x_S$ при ограничениях ${\sum }_{S\ni e}{x}_S\ge 1$ для всех $e$, $x_S\ge 0$.
Затем применять округление (например, пороговое или рандомизированное) — стандартный подход даёт аппроксимацию $O(\ln n)$ и часто практический результат лучше, плюс LP даёт нижнюю оценку для отбора.
- Примально-двойственные алгоритмы и жадные варианты с доработкой: похожи на классический greedy, но аккуратно масштабируют веса — улучшают стабильность и дают те же гаранты.
- Специальные методы для частных случаев: для геометрических покрытий, покрытий с ограниченной частотой элементов (element frequency $f$) можно получить приближения $f$ или $O(\log f)$, а иногда PTAS.
- Целочисленное программирование + MIP-решатель: для средних размеров инстансов часто даёт оптимум или очень хорошие решения.
Резюме: жадный прост и даёт гарантию $H_n\approx \ln n$, но может быть логарифмически хуже оптимума; в практике эффективны LP-округления, локальный поиск, примально-двойственные схемы и специальные эвристики в зависимости от структуры задачи.