Том 27, номер 3, 2020 г., Стр. 28-52

УДК 519.8
Глебов А. Н., Токтохоева С. Г.
Полиномиальный алгоритм с асимптотической оценкой точности 2/3 для несимметричной задачи об $m$ коммивояжёрах на максимум

Аннотация:
В 2005 г. Капланом и др. был разработан полиномиальный алгоритм с гарантированной оценкой точности 2/3 для несимметричного случая задачи коммивояжёра на максимум. В 2014 г. Глебов, Замбалаева и Скретнева получили алгоритм с такой же оценкой точности и кубической оценкой временной сложности для несимметричного случая задачи о двух коммивояжёрах на максимум, где требуется найти два рёберно не пересекающихся гамильтоновых цикла максимального суммарного веса в полном взвешенном $n$-вершинном ориентированном графе. Целью настоящей работы является построение аналогичного алгоритма для более общей задачи об $m$ коммивояжёрах на максимум в несимметричном случае и обоснование для этого алгоритма оценки точности,
асимптотически стремящейся к 2/3 с ростом $m$, и оценки временной сложности $O(mn^3)$.
Ил. 2, библиогр. 29

Ключевые слова: гамильтонов цикл, задача коммивояжёра, задача нескольких коммивояжёров, приближённый алгоритм, гарантированная оценка точности.

DOI: 10.33048/daio.2020.27.677

Глебов Алексей Николаевич ^1,2
Токтохоева Сурэна Гармажаповна ²
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: angle@math.nsc.ru, s.toktokhoeva@ya.ru

Статья поступила 2 декабря 2019 г.
После доработки — 9 мая 2020 г.
Принята к публикации 25 мая 2020 г.

Литература

[1] Krarup J. The peripatetic salesman and some related unsolved problems // Combinatorial programming: Methods and applications. Proc. NATO Adv. Study Inst. (Versailles, France, 1974). Dordrecht: Reidel, 1975. P. 173–178. (NATO Adv. Study Inst. Ser., Ser. C: Math. Phys. Sci.; Vol. 19).

[2] Агеев А. А., Бабурин А. Е., Гимади Э. Х. Полиномиальный алгоритм с оценкой 3/4 для нахождения двух рёберно не пересекающихся гамильтоновых циклов максимального суммарного веса // Дискрет. анализ и исслед. операций. Сер. 1. 2006. Т. 13, № 2. С. 11–20.

[3] Глебов А. Н., Замбалаева Д. Ж. Полиномиальный алгоритм с оценкой точности 7/9 для задачи о двух коммивояжёрах на максимум // Дискрет. анализ и исслед. операций. 2011. Т. 18, № 4. С. 17–48.

[4] Бабурин А. Е., Гимади Э. Х., Коркишко Н. М. Приближённые алгоритмы для нахождения двух рёберно не пересекающихся гамильтоновых циклов минимального веса // Дискрет. анализ и исслед. операций. Сер. 2. 2004. Т. 11, № 1. С. 11–25.

[5] Агеев А. А., Пяткин А. В. Приближённый алгоритм решения метрической задачи о двух коммивояжёрах с оценкой точности 2 // Дискрет. анализ и исслед. операций. 2009. Т. 16, № 4. С. 3–20.

[6] Glebov A. N., Gordeeva A. V. An algorithm with approximation ratio 5/6 for the Metric Maximum $m$-PSP // Discrete Optimization and Operations Research. Proc. 9th Int. Conf. DOOR 2016 (Vladivostok, Russia, Sep. 19–23, 2016). Heidelberg: Springer, 2016. P. 159–170. (Lect. Notes Comput. Sci.; Vol. 9869).

[7] Гимади Э. Х. Асимптотически точный алгоритм отыскания одного и двух рёберно не пересекающихся маршрутов коммивояжёра максимального веса в евклидовом пространстве // Тр. Ин-та математики и механики УрО РАН. 2008. Т. 14, № 2. С. 23–32.

[8] Бабурин А. Е., Гимади Э. Х. Об асимптотической точности эффективного алгоритма решения задачи $m$-PSP на максимум в многомерном евклидовом пространстве // Тр. Ин-та математики и механики УрО РАН. 2010. Т. 16, № 3. С. 12–24.

[9] Гимади Э. Х., Глазков Ю. В., Глебов А. Н. Приближённые алгоритмы решения задачи о двух коммивояжёрах в полном графе с весами рёбер 1 и 2 // Дискрет. анализ и исслед. операций. Сер. 2. 2007. Т. 14, № 2. С. 41–61.

[10] Глебов А. Н., Гордеева А. В., Замбалаева Д. Ж. Алгоритм с оценкой 7/5 для задачи о двух коммивояжёрах на минимум с различными весовыми функциями // Сиб. электрон. мат. изв. 2011. Т. 8. С. 296–309.

[11] Глебов А. Н., Замбалаева Д. Ж. Приближённый алгоритм решения задачи о двух коммивояжёрах на минимум с различными весовыми функциями // Дискрет. анализ и исслед. операций. 2011. Т. 18, № 5. С. 11–37.

[12] Гимади Э. Х., Ивонина Е. В. Приближённые алгоритмы решения задачи о двух коммивояжёрах на максимум // Дискрет. анализ и исслед. операций. Сер. 2. 2012. Т. 19, № 1. С. 17–32.

[13] Гордеева А. В. Полиномиальные алгоритмы с гарантированными оценками точности для метрической задачи о двух коммивояжёрах на максимум. Выпускная дипломная работа специалиста. Новосибирск: НГУ, 2010.

[14] Wolfler Calvo R., Cordone R. A heuristic approach to the overnight security service problem // Comput. Oper. Res. 2003. Vol. 30. P. 1269–1287.

[15] De Kort J. B. J. M. A branch and bound algorithm for symmetric 2-PSP // Eur. J. Oper. Res. 1993. Vol. 70. P. 229–243.

[16] De Kort J. B. J. M. Lower bounds for symmetric K-peripatetic salesman problems // Optimization. 1991. Vol. 22, No. 1. P. 113–122.

[17] De Kort J. B. J. M. Bounds for the symmetric 2-peripatetic salesman problem // Optimization. 1992. Vol. 23, No. 4. P. 357–367.

[18] De Brey M. J. D., Volgenant A. Well-solved cases of the 2-peripatetic salesman problem // Optimization. 1997. Vol. 39, No. 3. P. 275–293.

[19] The traveling salesman problem and its variations. Dordrecht: Kluwer Acad. Publ., 2002.

[20] Gimadi E. Kh. Approximation efficient algorithms with performance guarantees for some hard routing problems // Proc. II Int. Conf. “Optimization and Applications”, OPTIMA–2011 (Petrovac, Montenegro, Sept. 25–Oct. 2, 2011). Moscow: VTs RAN, 2011. P. 98–101.

[21] Kaplan H., Lewenstein M., Shafrir N., Sviridenko M. Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs // J. ACM. 2005. Vol. 52, No. 4. P. 602–626.

[22] Сердюков А. И. Алгоритм с оценкой для задачи коммивояжёра на максимум // Управляемые системы. Сб. науч. тр. Вып. 25. Новосибирск: Ин-т математики СО АН СССР, 1984. С. 80–86.

[23] Hassin R., Rubinstein S. Better approximations for max TSP // Inf. Process. Lett. 2000. Vol. 75, No. 4. P. 181–186.

[24] Paluch K., Mucha M., Madry A. A 7/9-approximation algorithm for the maximum traveling salesman problem // Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques. Proc. 12th Int. Workshop, APPROX 2009 and 13th Int. Workshop RANDOM 2009 (Berkeley, CA, USA, Aug. 21–23, 2009). Heidelberg: Springer, 2009. P. 298–311. (Lect. Notes Comput. Sci.; Vol. 5687).

[25] Dudycz S., Marcinkowski J., Paluch K., Rybicki B. A. A 4/5-approximation algorithm for the maximum traveling salesman problem // Integer Programming and Combinatorial Optimization. Proc. 19th Int. Conf. IPCO 2017 (Waterloo, ON, Canada, June 26–28, 2017). Cham: Springer, 2017. P. 173–185. (Lect. Notes Comput. Sci.; Vol. 10328).

[26] Глебов А. Н., Замбалаева Д. Ж., Скретнева А. А. 2/3-Приближённый алгоритм для несимметричной задачи о двух коммивояжёрах на максимум // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 6. С. 11–20.

[27] Глебов А. Н., Токтохоева С. Г. Полиномиальный 3/5-приближённый алгоритм для несимметричной задачи о трёх коммивояжёрах на максимум // Дискрет. анализ и исслед. операций. 2019. Т. 26, № 2. С. 30–59.

[28] Gabow H. N. An efficient reduction technique for degree-restricted subgraph and bidirected network flow problems // Proc. 15th Annu. ACM Symp. Theory of Comput. (Boston, USA, April 25–27, 1983). New York: ACM, 1983. P. 448–456.

[29] Cole R., Ost K., Schirra S. Edge-coloring bipartite multigraphs in $O$($E \times$ log $D$) time // Combinatorica. 2001. Vol. 21, No. 1. P. 5–12.