-якого? ? (0,1] існує алгоритм A?, Який знаходить упаковку з числом контейнерів не більше (1 + 2?) OPT + 1.
Трудомісткість A? полиномиально залежить від n.
(Без доведення).
.7. Алгоритм A?
. Видалити предмети з вагою менше? .
. Упорядкувати залишилися предмети і розбити їх на K =? 1 /? 2? груп.
3. У кожній групі збільшити ваги предметів до максимальної ваги в групі.
. Знайти оптимальну упаковку предметів, що мають тільки K різних ваг кожен з яких не менше? .
. Повернути вихідні ваги предметів і застосувати алгоритм FF для предметів з вагою менше? .
Негативний результат
Теорема. Для будь-якого? > 0 існування наближеного полиномиального алгоритму A з гарантованою точністю тягне P=NP.
Доказ. Нехай такий алгоритм А існує. Покажемо, як з його допомогою можна вирішити точно одну з NP-повних задач, а саме задачу про розбивку. Дано n невід'ємних чисел a1, ..., an.
Чи можна розбити їх на дві підмножини так, щоб сума чисел в кожному підмножині дорівнювала.
Розглянемо завдання упаковки в контейнери з вагами предметів wi=ai / C, i=1, ..., n. Якщо їх можна упакувати в два контейнери, відповідь в задачі
про розбивку - «ТАК». Застосуємо алгоритм А до задачі про контейнерах.
Якщо OPT=2, то алгоритм А теж дає 2, інакше, тобто алгоритм А точний.
.8. Релаксація лінійного програмування
Замінимо умова Булевой змінних на умови:
? yj? 1, j=1, ..., n
? xij? 1, i, j=1, ..., n.
Тоді одне з оптимальних рішень має вигляд
що дає нижню оцінку
(предмети можна різати довільним чином).
.9. Оцінки Martello & Toth
Для прикладу L={1, ..., n}, 0? wi < 1 і довільного 0? ? ? 1/2 покладемо
={i? L | wi> 1 -? } - Великі предмети={i? L | 1 -? ? wi> 1/2} - середні предмети={i? L | 1/2? wi? ? } - Дрібні предмети
Теорема. Для будь-якого 0? ? ? 1/2 величина є нижньою оцінкою для OPT (L).
Доказ. Кожен предмет з безлічі L1? L2 вимагає окремий контейнер. Тому в будь-якому допустимому рішенні не менш | L1 | + | L2 | контейнерів. Предмети з безлічі L3 чи не лежать разом з предметами з L1.
Значить, вони лежать або разом з предметами з L2, або в окремих контейнерах. У контейнерах для L2 залишилося вільного місця.
Отже, для предметів з безлічі L3 потрібно як мінімум окремих контейнерів.
Теорема. Для будь-якого 0? ? ? 1/2 величина
є нижньою оцінкою для OPT (L).
Доказ. Замінимо вага кожного предмета з безлічі L3 на? .
Тоді в один контейнер увійде предметів, і для безлічі L3 було б потрібно додатко...
