
Тип работы:	Предмет:	Язык работы:

ЭФФЕКТИВНЫЕ АЛГОРИТМЫ С ГАРАНТИРОВАННЫМИ ОЦЕНКАМИ ТОЧНОСТИ ДЛЯ НЕКОТОРЫХ ОБОБЩЕНИЙ ЗАДАЧИ КОММИВОЯЖЕРА

Работа №	102468
Тип работы	Авторефераты (РГБ)
Предмет	математика
Объем работы	19
Год сдачи	2017
Стоимость	2000 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено	126

Не подходит работа?

Узнай цену на написание

Содержание

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Публикации автора по теме диссертации
Статьи, опубликованные в журналах из списка ВАК

Введение

Актуальность темы. Предмет исследования диссертационной работы составляют труднорешаемые оптимизационные задачи, являющиеся обобщениями классической задачи коммивояжера (Traveling Salesman
Problem, TSP). В работе исследуются: задача о цикловом покрытии
фиксированной мощности k минимального веса (Minimum-weight k-Size
Cycle Cover Problem, Min-k-SCCP), обобщенная задача коммивояжера
(Generalized Traveling Salesman Problem, GTSP) и её геометрическая постановка евклидова обобщенная задача коммивояжера на сетке (Euclidean
Generalized Traveling Salesman Problem in k Grid Clusters, EGTSP-k-GC).
Результаты для близких постановок маршрутных задач были получены в работах Э.Х. Гимади, А.А. Агеева, Б. Манти, А.Г. Ченцова,
А. Григорьева и др.
Задача о цикловом покрытии графа фиксированного размера k минимального веса — это задача комбинаторной оптимизации, заключающаяся
в поиске оптимального покрытия полного взвешенного графа k вершиннонепересекающимися циклами. На содержательном уровне каждый цикл в
покрытии может трактоваться как маршрут для некоторого транспортного средства, посещающего соответствующее множество клиентов. С этой
точки зрения задача о цикловом покрытии близка к известной задаче
маршрутизации транспорта (Vehicle Routing Problem, VRP). С другой
стороны, при фиксированной единичной мощности циклового покрытия
задача совпадает с классической задачей коммивояжера. Кроме того, задача о цикловом покрытии мощности k занимает промежуточное положение в сложностной иерархии между эффективно разрешимой задачей
о назначениях и труднорешаемой задачей коммивояжера, что индуцирует дополнительный теоретический интерес к исследованию сложности и
аппроксимируемости Min-k-SCCP.
Постановка обобщенной задачи коммивояжера (Generalized Traveling
Salesman Problem, GTSP), известной в отечественной литературе под названием «задача обхода мегаполисов», задается полным взвешенным графом, множество вершин которого разбито на k непересекающихся кластеров, и заключается в поиске цикла минимального веса посещающего
каждый кластер.

Возникли сложности?

Нужна помощь преподавателя?

Помощь студентам в написании работ!

ДИПЛОМНЫЕ МАГИСТЕРСКИЕ ДИССЕРТАЦИИ

Курсовые Статьи Диплом Рязань

Литература

[1] Khachay M., Neznakhina K. Approximability of the minimum-weight k-size cycle cover problem //Journal of Global Optimization. - 2016. - Vol. 66. - №. 1. - P. 65-82. DOI: 10.1007/s10898-015-0391-3. (Web of science, Scopus)
[2] Хачай М.Ю., Незнахина Е.Д. Аппроксимируемость задачи о ми¬нимальном по весу цикловом покрытии графа // Доклады ака¬демии наук. - 2015. - Т. 461. - №. 6. - С. 644-649. DOI: 10.7868/S086956521512004X. (РИНЦ)
Khachai M.Y., Neznakhina E.D. Approximability of the problem about a minimum-weight cycle cover of a graph // Doklady Mathematics. - Pleiades Publishing, 2015. - Vol. 91. - №. 2. - P. 240-245. DOI: 10.1134/S1064562415020313. (Web of science, Scopus)
Neznakhina E.D. A PTAS for Min-k-SCCP in Euclidean space of arbitrary fixed dimension //Proceedings of the Steklov Institute of Mathematics. - 2016. - Vol. 295. - №. 1. - P. 120-130. DOI: 10.1134/S0081543816090133. (Web of science, Scopus)
[4] Хачай М.Ю., Незнахина Е.Д. Разрешимость обобщенной задачи коммивояжера в классе квази- и псевдопирамидальных маршрутов // Труды Института математики и механики УрО РАН. - 2017. - Т. 22. - №. 3 - С. 280-291. DOI: 10.21538/0134-4889-2017-23-3-280-291. (РИНЦ)
[5] Хачай М.Ю., Незнахина Е.Д. Приближенные схемы для обобщенной задачи коммивояжера //Труды Института математики и механики УрО РАН. - 2016. - Т. 22. - №. 3. - С. 283-292. DOI: 10.21538/0134¬4889-2016-22-3-283-292. (РИНЦ)
[6] Khachay M., Neznakhina K. Towards a PTAS for the generalized TSP in grid clusters //AIP Conference Proceedings. - AIP Publishing, 2016. - Vol. 1776. - №. 1. - P. 050003. DOI: 10.1063/1.4965324. (Web of science, Scopus)
[7] Khachay M., Neznakhina K. Polynomial Time Approximation Scheme for the Minimum-weight k-Size Cycle Cover Problem in Euclidean space of an arbitrary fixed dimension //IFAC-PapersOnLine. - 2016. - Vol. 49.
- №. 12. - P. 6-10. DOI: 10.1016/j.ifacol.2016.07.541. (Web of science, Scopus)
[8] Хачай М.Ю., Незнахина Е.Д. Полиномиальная приближенная схе¬ма для евклидовой задачи о цикловом покрытии графа // Труды Института математики и механики УрО РАН. - 2014. - Т. 20. - №. 4.
- С. 297-311. (РИНЦ)
Khachai M.Y., Neznakhina E.D. A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph // Proceedings of the Steklov Institute of Mathematics. - 2015. - Vol. 289.
- №. 1. - P. 111-125. DOI: 10.1134/S0081543815050107. (Web of science, Scopus)
Другие публикации
[9] Khachay M., Neznakhina K. Approximation Schemes for the Generalized TSP in Grid Clusters // VIII International Conference on Optimization Methods and Applications (Petrovac, Montenegro, October 2-7, 2017) :тез.докл. - Moscow, 2017, P. 81.
[10] Khachay M., Neznakhina K. Efficient optimal algorithm for the Quasipyramidal GTSP // 17th Baikal international school-seminar "Methods of Optimization and Their Applications"(Maksimikha, Russia, July 31 - August 6, 2017) :тез.докл. - Irkutsk, 2017, P. 109.
[11] Khachay M., Neznakhina K. Approximation Schemes for the Generalized TSP in Grid Clusters // VII International Conference on Optimization Methods and Applications (Petrovac, Montenegro, September 25 - October 2, 2016) :тез.докл. - Moscow, 2016, P. 88.
[12] Khachay M., Neznakhina K. Approximation Algorithms for Generalized TSP in Grid Clusters // CEUR Workshop Proceedings. - 2016. - Vol. 1623. - P. 39-48. (Scopus)
[13] Khachay M., Neznakhina K. Polynomial Time Approximation Scheme forEuclidean Minimum-weight k-Size Cycle CoverProblem in Rd// VI International Conference on Optimization Methods and Applications (Petrovac, Montenegro, September 27 - October 3, 2015) :тез.докл. - Moscow, 2015, P. 104.
[14] Khachay M., Neznakhina K. Polynomial Time Approximation Scheme for Euclidean Minimum-weight k-Size Cycle Cover Problem on the plane // 28th Conference of the European Chapter on Cobinatorial Optimization (Catania, Italy, 28-30 May 2015):тез.докл. - 2015, P. 29.
[15] Незнахина Е.Д., Хачай М.Ю. PTAS для евклидовой задачи Min- k-SCCP на плоскости для произвольных фиксированных значений параметра к // XV Всероссийская конференция "Математическое программирование и приложения"(Екатеринбург, Россия, 2-6 мар¬та 2015 г.) : тез.докл. - Екатеринбург, 2015, C. 151.
[16] Незнахина Е.Д. Аппроксимируемость евклидовой задачи о цикло¬вом покрытии графа произвольного фиксированного размера // Со¬временные проблемы математики и её приложений (г. Екатеринбург, 25-31 января 2015 г.) : Труды 46-й Международной молодежной школы-конференции - Екатеринбург, 2015, С. 115.
[17] Khachay M., Neznakhina E. Polynomial-time approximability of geometric multiple traveling salesmen problem // 10-я международная конференция Интеллектуализация обработки информации (о.Крит, Греция , 4-11 октября 2014 г.) : тез.докл. - Москва, 2014, P. 99.
[18] Khachay M., Neznakhina E. k-Minimum Hamiltonian Cycles Problem. Complexity and Approximability // V International Conference on Optimization Methods and Applications (Petrovac, Montenegro, September 2014) :тез.докл. - Moscow, 2014, P. 112.
[19] Khachay M., Neznakhina E. Approximation of k-Minimum Hamiltonian Cover Problem // 15th International Conference on Operational Research (Osijek, Croatia, 24-26 September 2014) :тез.докл. - 2014, P. 41.
[20] Хачай М.Ю., Незнахина Е.Д. Полиномиальная приближенная схе¬ма для задачи о разбиении полного евклидова графа на два гамиль¬тоновых цикла минимального веса // XVI Байкальская междуна¬родная школа-семинар, Методы оптимизации и их приложения (о. Ольхон, Байкал, 30 июня - 6 июля 2014 г.) : тез.докл. - Красноярск, 2014, С. 88.
[21] Незнахина Е.Д. PTAS для некоторых обобщений евклидовой задачи TSP // Современные проблемы математики и её приложений (г. Екатеринбург, 2-8 февраля 2014 г.) : Труды 45-й Международной молодежной школы-конференции - Екатеринбург, 2014, С. 181.