Полиномиальная аппроксимируемость асимметричной задачи о покрытии графа ограниченным числом циклов

Standard

Полиномиальная аппроксимируемость асимметричной задачи о покрытии графа ограниченным числом циклов. / Хачай, Михаил Юрьевич ; Незнахина, Екатерина Дмитриевна; Рыженко, К. В.
в: Труды института математики и механики УрО РАН, Том 29, № 3, 2023, стр. 261-273.

Результаты исследований: Вклад в журнал › Статья › Рецензирование

BibTeX

@article{c799b448366943a790f8fbf53e90605c,

title = "Полиномиальная аппроксимируемость асимметричной задачи о покрытии графа ограниченным числом циклов",

abstract = "В недавних работах О. Свенссона и В. Трауб впервые обоснована аппроксимируемость асимметричной задачи коммивояжера (ATSP) в классе алгоритмов с фиксированными гарантиями точности. Как и знаменитый алгоритм Кристофидеса - Сердюкова для симметричных маршрутных задач, данные прорывные результаты, применяемые в качестве {"}черного ящика{"}, позволили разработать первые полиномиальные приближенные алгоритмы с константными факторами аппроксимации для серии близких комбинаторных задач. Одновременно выявились задачи, в которых этот простой подход, основанный на сведении исходной задачи к одной или нескольким вспомогательным постановкам задачи коммивояжера, не приводит к успеху. В данной статье подход Свенссона - Трауб распространяется на более широкий класс задач о покрытии минимального веса взвешенного ориентированного графа ограниченным сверху числом циклов. В частности, впервые показывается, что задача о покрытии графа не более чем k циклами допускает полиномиальную аппроксимацию с константной точностью max{22+ε,4+k} для произвольного ε>0.",

author = "Хачай, {Михаил Юрьевич} and Незнахина, {Екатерина Дмитриевна} and Рыженко, {К. В.}",

note = "Исследования поддержаны Российским научным фондом, грант № 22-21-00672, https://rscf.ru/ project/22-21-00672/.",

year = "2023",

doi = "10.21538/0134-4889-2023-29-3-261-273",

language = "Русский",

volume = "29",

pages = "261--273",

journal = "Труды института математики и механики УрО РАН",

issn = "0134-4889",

publisher = "Институт математики и механики им. Н.Н. Красовского УрО РАН",

number = "3",

}

RIS

TY - JOUR

T1 - Полиномиальная аппроксимируемость асимметричной задачи о покрытии графа ограниченным числом циклов

AU - Хачай, Михаил Юрьевич

AU - Незнахина, Екатерина Дмитриевна

AU - Рыженко, К. В.

N1 - Исследования поддержаны Российским научным фондом, грант № 22-21-00672, https://rscf.ru/ project/22-21-00672/.

PY - 2023

Y1 - 2023

N2 - В недавних работах О. Свенссона и В. Трауб впервые обоснована аппроксимируемость асимметричной задачи коммивояжера (ATSP) в классе алгоритмов с фиксированными гарантиями точности. Как и знаменитый алгоритм Кристофидеса - Сердюкова для симметричных маршрутных задач, данные прорывные результаты, применяемые в качестве "черного ящика", позволили разработать первые полиномиальные приближенные алгоритмы с константными факторами аппроксимации для серии близких комбинаторных задач. Одновременно выявились задачи, в которых этот простой подход, основанный на сведении исходной задачи к одной или нескольким вспомогательным постановкам задачи коммивояжера, не приводит к успеху. В данной статье подход Свенссона - Трауб распространяется на более широкий класс задач о покрытии минимального веса взвешенного ориентированного графа ограниченным сверху числом циклов. В частности, впервые показывается, что задача о покрытии графа не более чем k циклами допускает полиномиальную аппроксимацию с константной точностью max{22+ε,4+k} для произвольного ε>0.

AB - В недавних работах О. Свенссона и В. Трауб впервые обоснована аппроксимируемость асимметричной задачи коммивояжера (ATSP) в классе алгоритмов с фиксированными гарантиями точности. Как и знаменитый алгоритм Кристофидеса - Сердюкова для симметричных маршрутных задач, данные прорывные результаты, применяемые в качестве "черного ящика", позволили разработать первые полиномиальные приближенные алгоритмы с константными факторами аппроксимации для серии близких комбинаторных задач. Одновременно выявились задачи, в которых этот простой подход, основанный на сведении исходной задачи к одной или нескольким вспомогательным постановкам задачи коммивояжера, не приводит к успеху. В данной статье подход Свенссона - Трауб распространяется на более широкий класс задач о покрытии минимального веса взвешенного ориентированного графа ограниченным сверху числом циклов. В частности, впервые показывается, что задача о покрытии графа не более чем k циклами допускает полиномиальную аппроксимацию с константной точностью max{22+ε,4+k} для произвольного ε>0.

UR - https://elibrary.ru/item.asp?id=54393179

UR - http://www.scopus.com/inward/record.url?partnerID=8YFLogxK&scp=85180580823

UR - https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=tsmetrics&SrcApp=tsm_test&DestApp=WOS_CPL&DestLinkType=FullRecord&KeyUT=001148521600017

U2 - 10.21538/0134-4889-2023-29-3-261-273

DO - 10.21538/0134-4889-2023-29-3-261-273

M3 - Статья

VL - 29

SP - 261

EP - 273

JO - Труды института математики и механики УрО РАН

JF - Труды института математики и механики УрО РАН

SN - 0134-4889

IS - 3

ER -

ID: 46112767