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