Задача о рюкзаке: PTAS

Алгоритмы динамического программирования для задачи о рюкзаке дают точное решение за время O(nf^*) или O(nB). Если величины f^* и B не ограничена сверху никаким полиномом (то есть имеются большие коэффициенты), то эти псевдополиномиальные алгоритмы не является полиномиальными.

Однако, существует общий метод (который условно можно назвать «масштабированием»), позволяющий перейти к задаче с небольшими коэффициентами в целевой функции, оптимум которой не сильно отличается от оптимума исходной задачи.

Если мы отмасштабируем коэффициенты c1,…,cn, поделив нацело их на некоторый параметр scale, решим «отмасштабированную» задачу, и затем снова умножим коэффициенты на параметр scale, то очевидно, что мы получим допустимое решение исходной задачи и абсолютная погрешность стоимости «округленного и восстановленного» набора не превосходит величины n⋅scale.

Если потребовать, чтобы эта величина не превосходила ε1+εf∗, то получим, что каждое допустимое решение исходной задачи отличается от решения «отмасштабированной» задачи не более, чем на эту же величину.

Обозначая оптимум «отмасштабированной» задачи через f˜, получаем, что f˜≥f∗−ε1+εf∗=f∗(1+ε), то есть оптимум «отмасштабированной» задачи отличается от оптимума исходной задачи не более, чем в 1+ε раз.

При этом величина значение оптимального решения для «отмасштабированной» задачи уменьшается не менее, чем в scale раз по сравнению с исходной. И таким образом, для отмасштабированной задачи, версия алгоритма, ориентированная на отбор «самых легких решений» будет работать существенно меньшее время.

Однако проблема состоит в том, что в момент масштабирования мы не знаем величины оптимума f^*, и не можем выбрать коэффициент scale, который, чтобы решение было 1+ε-оптимальным, не должен превышать εf∗n(1+ε), с одной стороны, с другой — желательно максимально приблизить его к этой оценке, чтобы уменьшить коэффициенты в задаче.

Поэтому, важное наблюдение состоит в том, что вместо f^* можно рассматривать нижнюю оценку f^*, обозначим ее f_lb, и выбирать параметр масштабирования scale=εflbn(1+ε) тогда все вышеизложенные соображения о точности «отмасштабированного» решения сохранят силу.

Таким образом, стоит задача выбора нижней оценки f_lb, которую можно найти быстро с одной стороны, и желательно чтобы она была как можно ближе к f^*, так как это даст возможность увеличить коэффициент scale, и тем самым, сильнее уменьшить коэффициенты c1,…,cn и время выполнения алгоритма. Таким образом, общая схема алгоритма, представлена как процедура «knapsack_ptas_generic», которой на вход, кроме обычных параметров рюкзака, передают функцию «f_lower_bound», используемую для получения нижней оценки стоимости решения.

Осталось найти такую функцию. Например, можно рассмотреть тривиальную аппроксимацию ncmax≥f∗≥flb≡cmax,, где cmax=maxici; и получим функцию «knapsack_ptas_trivial».

Какова сложность этого алгоритма? Она, есть величина O(nf˜). Учитывая, что f∗≤ncmax, а f˜≤ncmaxscale, получаем оценку сложности алгоритма «knapsack_ptas_trivial»: O(nf˜)=On2cmaxscale=On3(1+ε)ε=On3ε.

Можно ли улучшить эту оценку? Ответ на этот вопрос положителен.

Для этого рассмотрим менее наивную аппроксимацию величины f^*, используя задача о рюкзаке: жадный алгоритм, дающий точность не хуже чем в два раза.

Используя эту оценку, получаем функцию «knapsack_ptas_nontrivial» Аналогично получаем оценку сложности для этого алгоритма: O(nf˜)=OnfGscale=On2(1+ε)ε=On2ε.