|
Труды Института математики и механики УрО РАН, 2014, том 20, номер 4, страницы 297–311
(Mi timm1135)
|
|
|
|
Эта публикация цитируется в 11 научных статьях (всего в 11 статьях)
Полиномиальная приближенная схема для евклидовой задачи о цикловом покрытии графа
М. Ю. Хачайab, Е. Д. Незнахинаba a Институт математики и механики им. Н. Н. Красовского УрО РАН
b Уральский федеральный университет им. Б. Н. Ельцина
Аннотация:
Изучается задача Min-$k$-SCCP о разбиении полного взвешенного орграфа на $k$ вершинно-непересекающихся циклов минимального суммарного веса, являющаяся естественным обобщением известной задачи коммивояжера (TSP) и обладающая рядом практических приложений в исследовании операций и анализе данных. Показано, что задача в общем случае $NP$-трудна в сильном смысле и сохраняет свойство труднорешаемости даже в геометрической постановке. Для метрического случая предложен $2$-приближенный алгоритм. Для евклидовой задачи Min-$2$-SCCP построена полиномиальная приближенная схема, основанная на подходе С. Ароры.
Ключевые слова:
$NP$-трудная задача, полиномиальная приближенная схема (PTAS), задача коммивояжера (TSP), цикловое покрытие размера $k$.
Поступила в редакцию: 13.08.2014
Образец цитирования:
М. Ю. Хачай, Е. Д. Незнахина, “Полиномиальная приближенная схема для евклидовой задачи о цикловом покрытии графа”, Тр. ИММ УрО РАН, 20, № 4, 2014, 297–311; Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 111–125
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/timm1135 https://www.mathnet.ru/rus/timm/v20/i4/p297
|
Статистика просмотров: |
Страница аннотации: | 349 | PDF полного текста: | 114 | Список литературы: | 53 | Первая страница: | 5 |
|