Войти / Регистрация
Корзина

  • Ваша корзина пуста
Войти / Регистрация
Корзина

  • Ваша корзина пуста

Статья «ОЦЕНКА АБСОЛЮТНОЙ ПОГРЕШНОСТИ И ПОЛИНОМИАЛЬНОЙ РАЗРЕШИМОСТИ ДЛЯ КЛАССИЧЕСКОЙ NP-ТРУДНОЙ ЗАДАЧИ ТЕОРИИ РАСПИСАНИЙ, "Доклады Академии наук"»

Авторы:
  • ЛАЗАРЕВ А.А.1
  • АРХИПОВ Д.И.2
стр. 523-527
Платно
1 Институт проблем управления им. В.А. Трапезникова РАН, Москва; Национальный исследовательский университет Высшая школа экономики, Москва, Московский государственный университет им. М.В.Ломоносова, Московский физико-технический институт, 2 Институт проблем управления им. В.А. Трапезникова РАН, Москва
Аннотация:
Предложен метод нахождения приближённого решения NP-трудных задач теории расписаний. Для задачи минимизации максимального временно`го смещения показано, как с помощью метрики, введённой на пространстве примеров задачи, можно использовать полиномиально разрешимые области для нахождения приближённого решения с гарантированной абсолютной погрешностью. Приведена теоретическая и экспериментальная оценка метода, а также сравнительный анализ с ED-эвристикой. Предложена численная характеристика полиномиальной неразрешимости задачи - верхняя оценка на гарантированную абсолютную погрешность для каждого класса эквивалентности пространства примеров.

Архивные статьи (2015 год и ранее) доступны для ознакомления бесплатно, для скачивания их необходимо приобрести. Для просмотра материалов необходимо зарегистрироваться и авторизоваться на сайте.

Чтобы приобрести доступ к материалу для юридического лица, пожалуйста, свяжитесь с администрацией портала с помощью формы обратной связи либо по электронному адресу libnauka@naukaran.com.  

Действия с материалами доступны только авторизованным пользователям.