|
|
Семинар отдела математического программирования
18 апреля 2014 г. 11:00–12:00, г. Екатеринбург, ул. Софьи Ковалевской, 16, актовый зал Института математики и механики УрО РАН, Екатеринбург
|
 |
|
 |
|
|
|
Полиномиальная приближенная схема для задачи о разбиении полного евклидового графа на два гамильтоновых цикла минимального веса
М. Ю. Хачайab, Незнахина Е.Д.b
a Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург
b Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, г. Екатеринбург
|
| Количество просмотров: |
| Эта страница: | 293 |
|
Аннотация:
В данной работе предлагается обобщение PTAS Ароры для евклидовой задачи о двух коммивояжерах на плоскости. Постановка данной задачи отличается от постановки классической задачи коммивояжера тем, что требуется указать два замкнутых, вершинно непересекающихся маршрута минимальной суммарной длины, посещающих все вершины исходного графа по одному разу.
|
|
Обратная связь: