ПРИБЛИЖЕННЫЕ АЛГОРИТМЫ С ФИКСИРОВАННЫМИ ОЦЕНКАМИ ТОЧНОСТИ ДЛЯ СЕРИИ АСИММЕТРИЧНЫХ ЗАДАЧ МАРШРУТИЗАЦИИ

Standard

ПРИБЛИЖЕННЫЕ АЛГОРИТМЫ С ФИКСИРОВАННЫМИ ОЦЕНКАМИ ТОЧНОСТИ ДЛЯ СЕРИИ АСИММЕТРИЧНЫХ ЗАДАЧ МАРШРУТИЗАЦИИ. / Незнахина, Екатерина Дмитриевна ; Огородников, Юрий Юрьевич; Рыженко, Ксения Валерьевна et al.
In: Доклады Российской академии наук. Математика, информатика, процессы управления, Vol. 514, No. 1, 2023, p. 89-97.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{e6f3543a42014c36a2f16d5d27a63f86,

title = "ПРИБЛИЖЕННЫЕ АЛГОРИТМЫ С ФИКСИРОВАННЫМИ ОЦЕНКАМИ ТОЧНОСТИ ДЛЯ СЕРИИ АСИММЕТРИЧНЫХ ЗАДАЧ МАРШРУТИЗАЦИИ",

abstract = "Обосновываются первые алгоритмы с константными оценками точности для серии асимметричных постановок задач маршрутизации: задачи о штейнеровском цикле, задачи коммивояжера с призами, задачи о покрытии графа ограниченным числом циклов и др. В большинстве своем предложенные алгоритмы опираются на оригинальные схемы сведения исследуемых постановок к вспомогательным постановкам асимметричной задачи коммивояжера и прорывные результаты О. Свенссона, Я. Тарнавски, Л. Вега и В. Трауб, Й. Вигена в области эффективной аппроксимируемости данной задачи. Алгоритм для задачи о покрытии графа ограниченным числом циклов опирается на технику, связанную с более глубокой модификацией подхода Свенссона-Трауб.",

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

year = "2023",

doi = "10.31857/S268695432360218X",

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

volume = "514",

pages = "89--97",

journal = "Доклады Российской академии наук. Математика, информатика, процессы управления",

issn = "2686-9543",

publisher = "Российская академия наук",

number = "1",

}

RIS

TY - JOUR

T1 - ПРИБЛИЖЕННЫЕ АЛГОРИТМЫ С ФИКСИРОВАННЫМИ ОЦЕНКАМИ ТОЧНОСТИ ДЛЯ СЕРИИ АСИММЕТРИЧНЫХ ЗАДАЧ МАРШРУТИЗАЦИИ

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

AU - Огородников, Юрий Юрьевич

AU - Рыженко, Ксения Валерьевна

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

PY - 2023

Y1 - 2023

N2 - Обосновываются первые алгоритмы с константными оценками точности для серии асимметричных постановок задач маршрутизации: задачи о штейнеровском цикле, задачи коммивояжера с призами, задачи о покрытии графа ограниченным числом циклов и др. В большинстве своем предложенные алгоритмы опираются на оригинальные схемы сведения исследуемых постановок к вспомогательным постановкам асимметричной задачи коммивояжера и прорывные результаты О. Свенссона, Я. Тарнавски, Л. Вега и В. Трауб, Й. Вигена в области эффективной аппроксимируемости данной задачи. Алгоритм для задачи о покрытии графа ограниченным числом циклов опирается на технику, связанную с более глубокой модификацией подхода Свенссона-Трауб.

AB - Обосновываются первые алгоритмы с константными оценками точности для серии асимметричных постановок задач маршрутизации: задачи о штейнеровском цикле, задачи коммивояжера с призами, задачи о покрытии графа ограниченным числом циклов и др. В большинстве своем предложенные алгоритмы опираются на оригинальные схемы сведения исследуемых постановок к вспомогательным постановкам асимметричной задачи коммивояжера и прорывные результаты О. Свенссона, Я. Тарнавски, Л. Вега и В. Трауб, Й. Вигена в области эффективной аппроксимируемости данной задачи. Алгоритм для задачи о покрытии графа ограниченным числом циклов опирается на технику, связанную с более глубокой модификацией подхода Свенссона-Трауб.

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

U2 - 10.31857/S268695432360218X

DO - 10.31857/S268695432360218X

M3 - Статья

VL - 514

SP - 89

EP - 97

JO - Доклады Российской академии наук. Математика, информатика, процессы управления

JF - Доклады Российской академии наук. Математика, информатика, процессы управления

SN - 2686-9543

IS - 1

ER -

ID: 51707300