Отсутствие аппроксимационного алгоритма для задачи о ранце

Question

Я работаю над следующим упражнением: Докажите, что если $ P \ neq NP $, не может существовать алгоритм аппроксимации $ A $ для задачи о рюкзаке (KP) такой, что $ \ Существует k \ in \ mathhbb {N} , \ forall I \ in S: OPT (I) - P_A (I) \ leq k $, где $ OPT (I) $ - оптимальная прибыль в экземпляре $ I $, а $ P_A (I) $ - прибыль, рассчитанная в $ A $.

Я знаю, что для КП существует FPTAS $ A '$, который гарантирует решение с прибылью $ P_ {A'} (I) \ geq (1 - \ varepsilon) OPT (I) $ в любом случае $ I $ и $ \ varepsilon> 0 $.

Мой подход - создать противоречие. Для этого я рассматриваю $ A = A '$ и стремлюсь показать, что $ P_A (I) \ geq (1 - \ varepsilon) OPT (I) \ geq ... \ geq OPT (I) - c $, где $ c \ в (0,1) $ постоянная. Таким образом, для адекватного выбора $ \ varepsilon $ я бы показал, что мы получаем оптимальное решение за полиномиальное время. Однако я изо всех сил пытаюсь выбрать $ \ varepsilon $.

Мне нужен совет, как поступить. Большое спасибо заранее!

Answer 1

Противоречие немного более тонкое.

Рассмотрим экземпляр I', полученный из I путем увеличения всех значений элементов в I n -кратном выражении.Оптимальная прибыль Opt(I') равна n -x, а оптимальная прибыль Opt(I), и решение обеих проблем состоит из одного и того же набора предметов (докажите это!).

Итак, если A находит решение Opt(I') - k, оно также находит Opt(I) - k/n.Если сделать n достаточно большим, то сделать вывод, что A разрешит любой экземпляр I лучше, чем Opt(I) * (1 - eps) для любого заданного eps.

Для целочисленных значений достаточновозьми любой n > k.Для реальных значений вам нужно еще немного поработать, а именно доказать, что A' не универсален, а должен зависеть от eps.