|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Оценка абсолютной погрешности и полиномиальной разрешимости для классической NP-трудной задачи теории расписанийстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАКСтатья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 22 февраля 2019 г.
- Авторы: Лазарев А.А., Архипов Д.И.
- Журнал: Доклады Академии наук
- Том: 480
- Номер: 5
- Год издания: 2018
- Издательство: ФГБУ "Издательство "Наука"
- Местоположение издательства: Москва
- Первая страница: 523
- Последняя страница: 527
- DOI: 10.7868/S0869565218050031
- Аннотация: Предложен метод нахождения приближённого решения NP-трудных задач теории расписаний. Для задачи минимизации максимального временно`го смещения показано, как с помощью метрики, вве- дённой на пространстве примеров задачи, можно использовать полиномиально разрешимые области для нахождения приближённого решения с гарантированной абсолютной погрешностью. Приведена теоретическая и экспериментальная оценка метода, а также сравнительный анализ с ED-эвристикой. Предложена численная характеристика полиномиальной неразрешимости задачи – верхняя оценка на гарантированную абсолютную погрешность для каждого класса эквивалентности пространства примеров.
- Добавил в систему: Лазарев Александр Алексеевич
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | 30484-46781.pdf | 30484-46781.pdf | 286,7 КБ | 6 сентября 2018 [Lazarev] |