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

Перейти к навигации Перейти к поиску
м
 
Строка 66: Строка 66:


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




4431

правка

Навигация