М. Ю. Хачай, Ю. Ю. Огородников, “Эффективная аппроксимируемость задачи об оптимальной маршрутизации в метрических пространствах фиксированной размерности удвоения”, Докл. РАН. Матем., информ., проц. упр., 2020, том 493,страницы 74

Эта публикация цитируется в 5 статьях

ИНФОРМАТИКА

Эффективная аппроксимируемость задачи об оптимальной маршрутизации в метрических пространствах фиксированной размерности удвоения

М. Ю. Хачай^abc, Ю. Ю. Огородников^ab

^a Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, Екатеринбург, Россия
^b Уральский федеральный университет им. Б. Н. Ельцина, Екатеринбург, Россия
^c Омский государственный университет, Омск, Россия

Аннотация: Впервые обосновывается аппроксимируемость известной труднорешаемой задачи о маршрутизации транспортных средств ограниченной грузоподъемности в метрических пространствах произвольной фиксированной размерности удвоения в классе квазиполиномиальных приближенных схем.

Ключевые слова: задача маршрутизации транспорта ограниченной грузоподъемности, метрическое пространство фиксированной размерности удвоения, квазиполиномиальная приближенная схема.

УДК: 519.8

Статья представлена к публикации: К. В. Рудаков
Поступило: 26.05.2020
После доработки: 01.06.2020
Принято к публикации: 02.06.2020

DOI: 10.31857/S2686954320040086