Семинары: М. Ю. Хачай, Незнахина Е.Д., Полиномиальная приближенная схема для задачи о разбиении полного евклидового графа на два гамильтоновых цикла минимального веса

СЕМИНАРЫ


Семинар отдела математического программирования 18 апреля 2014 г. 11:00, г. Екатеринбург, ул. Софьи Ковалевской, 16, актовый зал Института математики и механики УрО РАН, Екатеринбург

Полиномиальная приближенная схема для задачи о разбиении полного евклидового графа на два гамильтоновых цикла минимального веса М. Ю. Хачай^ab, Незнахина Е.Д.^b ^a Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург ^b Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, г. Екатеринбург
Аннотация: В данной работе предлагается обобщение PTAS Ароры для евклидовой задачи о двух коммивояжерах на плоскости. Постановка данной задачи отличается от постановки классической задачи коммивояжера тем, что требуется указать два замкнутых, вершинно непересекающихся маршрута минимальной суммарной длины, посещающих все вершины исходного графа по одному разу.