Аппроксимационные схемы для задачи об упаковке в контейнеры: различия между версиями

Исходными данными для задачи упаковки в контейнеры является набор <math>I</math> из n предметов, заданных их размерами <math>s_1, ..., s_n</math>, где каждый размер <math>s_i</math> представляет собой вещественное число в диапазоне (0, 1]. Подмножество предметов <math>S \subseteq I</math> может быть упаковано в контейнер, если общий размер предметов в S не превышает 1. Задача заключается в том, чтобы упаковать все предметы из I в минимальное количество контейнеров. Обозначим за OPT(I) значение оптимального решения, а за Size(I) – общий размер всех предметов в I. Очевидно, что <math>OPT(I) \ge \lceil Size(I) \rceil</math>.

Строго говоря, для этой задачи не допускается наличие алгоритма полиномиального времени с гарантией аппроксимации лучше 3/2. Любопытно, однако, что это не исключает существования алгоритма, требующего, скажем, OPT(I) + 1 контейнеров (в отличие от других задач оптимизации, в случае упаковки в контейнеры создание нескольких копий маленького «сложного экземпляра задачи» для получения сложного экземпляра величины не работает). Более осмысленно рассматривать гарантии аппроксимации в асимптотическом смысле.