и, кроме того, для любого S из семейства Т мы вскоре докажем, что

J2cxH(\S\).

xES

Из неравенств (37.9) и (37.10) следует, что

с<: Y,H(\s\)<:

sec*

<С \С*\ •Я(тах{5 : S G Г}),

что и составляет утверждение теоремы.

Осталось доказать неравенство (37.10). Пусть S - произвольное множество из семейства J7, содержащее и элементов. Каждый из этих элементов получит какую-то сумму денег по нашим правилам, и надо проверить, что общая сумма для всех элементов S не превосходит суммы

1 + 1/2+1/3 + ...+ 1/и

(эта сумма также состоит из и слагаемых). Сейчас мы в этом убедимся. Посмотрим на группу элементов S, которые получают свои деньги первыми (среди элементов S). Каждый из них получит не более 1/и. В самом деле, общее количество элементов X, получающих деньги на этом шаге, не может быть меньше и, ведь жадный алгоритм выбирает множество, покрывающее наибольшее возможное число ещё не покрытых элементов, и не может выбрать множества, худшего S. Значит, на каждый элемент придется не более 1/и, и общая сумма будет не больше, чем хвост нашей суммы, имеющий ту же длину. После этого останется какое-то число щ непокрытых элементов, и надо будет доказать, что общая сумма денег, им причитающаяся, не превосходит оставшейся части нашей суммы, то есть

1+1/2+1/3+... + 1/и1

Посмотрим на элементы, которые будут получать деньги первыми (среди оставшихся): по тем же причинам, что и раньше, они получат не более 1/щ каждый, и общая сумма не будет превосходить соответствующей части нашей суммы. Продолжая это рассуждение, мы видим, что если выплаты происходят в к этапов и если

Щ и2 ... ик = 0

- количество элементов в S, которым ещё не выдали денег после 1,2,... , к выплат, то общая сумма выплаченных элементам S денег не превосходит

1 11 11111 -+ •••+-+-+ •••+-+ ...+ - + ...+ - + - + ...+ -,

что не превосходит (сравниваем почленно) частной суммы гармонического ряда

11111111

1Uk-l ик-\ + 1Uk-2Щ + 1щ щ + 1и

то есть Н(и), что завершает доказательство неравенства (37.10) и теоремы 37.4

[Вадик: надо бы набрать соответствующие члены один под другим!!]

Следствие 37.4.

Алгоритм Greedy-Set-Cover даёт решение задачи о покрытии, худшее оптимального не более чем в (In А + 1) раз.

Доказательство. Очевидное следствие теоремы 37.3 и неравенства (3.12).

Если множества, из которых надо выбирать покрытие, содержат мало элементов, то алгоритм Greedy-Set-Cover даёт решение, довольно близкое к оптимальному. Например, если мы применяем этот алгоритм к задаче о вершинном покрытии графа, в котором степени вершин не превосходят 3, то даваемое им решение не более чем в Н(3) = 11/6 раз хуже оптимального. (Эта оценка немного лучше, чем для приведённого в разделе 37.1 алгоритма Approx-Vertex-Cover.)

Упражнения.

37.3-1

Рассмотрим каждое из слов arid, dash, drain, heard, lost, nose, shun, slate, snare, thread как множество букв. Что даст алгоритм Greedy-Set-Cover в применении к этим множествам? (Если возникает выбор между несколькими словами, берётся первое в алфавитном порядке.)

37.3-2

Покажите, что задача о покрытии множествами, рассматриваемая как задача разрешения, является NP-полной, сведя к ней задачу о вершинном покрытии.

37.3-3

Показать, что можно реализовать алгоритм Greedy-Set-Cover с временем работы 0(2Se:F \$\)-37.3-4

Объясните, почему следующее ослабление утверждения теоремы 37.4 очевидно:

\С\ \C*\-max{\S\ : S G Т}.

37.5

Приведите примеры, показывающие, что количество различных ответов, даваемых алгоритмом Greedy-Set-Cover при разных способах выбора множества в строке 4 (из множеств, покрывающих одинаковое число ещё не покрытых элементов), может экспоненциально расти с ростом размера задачи.

37.3. Задача о сумме подмножества

Исходным данным для этой задачи является пара (S,t), где S = {х\, Х2, , хп} представляет собой некоторое множетсво положительных целых чисел, а £ - положительное целое число. Зная Sat, надо выяснить, можно ли найти подмножество множества S, сумма элементов которого в точности равна t. Эта задача является NP-полной (см. раздел 36.5.3).

Задачу можно ставить и в оптимизационном варианте, требуя отыскать среди подмножеств, сумма которых не превосходит t, такое, у которого сумма ближе всего к t. Можно представлять себе, что мы должны как можно больше загрузить машину грузоподъёмности t, имея ящики весов х\,... ,хп (но не переходя границы).

В этом разделе мы приводим алгоритм, решающий эту задачу за экспоненциальное время, и показываем, как из него получить полностью полиномиальную схему приближения. (Напомним: это означает, что время работы оценивается многочленом от размера задачи и от 1/е, где е - относительная ошибка.)

Экспоненциальный алгоритм

Если L - набор чисел, а ж - некоторое число, то через L + ж мы обозначаем набор чисел, который получится, если добавить ж к каждому из элементов L. Например, для L = (1, 2, 3, 5, 9) и ж = 2 мы имеем L + ж = (3, 4, 5, 7,11). Аналогичная запись используется и для множеств:

S + х = {s + х : s £ S}

Нам понадобится процедура Merge-Lists(L, V), результатом которой является соединение двух упорядоченных наборов L и V с сохранением порядка. Вспоминая сортировку слиянием (раздел 1.3.1). мы видим, что это можно сделать за время 0(£ + С). (Мы не приводим текста этой процедуры.)

Теперь мы можем написать алгоритм Exact-Subset-Sum, решающий сформулированную выше задачу о сумме подмножества. Исходными данными для него является набор положительных целых чисел S = (х\,Х2, ,хп) и положительное целое число t. Результатом работы является максимально возможная сумма некоторых элементов из S, не превосходящая t.

Exact-Subset-Sum (S,t)

1n <- SI

2L 0 <- <0>

3for i<-l 1 to n

4do L i <- Merge-Lists(L {i-l>, L {i-l>+x i)

5удалить из $L i$ элементы, большие $t$

6return наибольший элемент в $L n$