|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Оценка абсолютной погрешности и полиномиальной разрешимости для классической $NP$-трудной задачи теории расписаний
А. А. Лазаревabcd, Д. И. Архиповa a Институт проблем управления им. В. А. Трапезникова РАН, Москва
b Национальный исследовательский университет "Высшая школа экономики", Москва
c Московский государственный университет имени М. В. Ломоносова
d Московский физико-технический институт
Аннотация:
Предложен метод нахождения приближённого решения $NP$-трудных задач теории расписаний. Для задачи минимизации максимального временно`го смещения показано, как с помощью метрики, введённой на пространстве примеров задачи, можно использовать полиномиально разрешимые области для нахождения приближённого решения с гарантированной абсолютной погрешностью. Приведена теоретическая и экспериментальная оценка метода, а также сравнительный анализ с $ED$-эвристикой. Предложена численная характеристика полиномиальной неразрешимости задачи - верхняя оценка на гарантированную абсолютную погрешность для каждого класса эквивалентности пространства примеров.
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dan47503
|
Статистика просмотров: |
Страница аннотации: | 48 |
|