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

Помимо NP-трудности, другие показатели трудности не известны; возможно, что для данной задачи существует алгоритм с полиномиальным временем выполнения и гарантией OPT + 1. Решение этой задачи является ключевым открытым вопросом. Перспективным представляется подход с использованием упомянутой выше конфигурационной LP. На самом деле, не известно ни одного экземпляра задачи, для которого аддитивный разрыв между оптимальным решением конфигурационной ЛП и оптимальным целочисленным решением был бы больше 1. Было бы очень интересно спроектировать экземпляр, для которого аддитивный разрыв целостности был бы равен двум или более.