Том 26, номер 2, 2019 г., Стр. 30-59

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

Аннотация:
Разработан первый полиномиальный приближённый алгоритм с гарантированной оценкой точности для несимметричного случая задачи о трёх коммивояжёрах на максимум, где требуется найти три рёберно непересекающихся гамильтоновых цикла максимального суммарного веса в полном взвешенном ориентированном графе. Для полученного алгоритма обоснована гарантированная оценка точности 3\5 и кубическая оценка временной сложности.
Ил. 18, библиогр. 27.

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

DOI: 10.33048/daio.2019.26.622

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

Статья поступила 6 июня 2018 г.
После доработки — 27 ноября 2018 г.
Принята к публикации 28 ноября 2018 г.

Литература

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

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

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

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

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

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

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

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

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

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

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

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

[13] 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.

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

[15] De Kort J. B. J. M. Upper bounds for the symmetric 2-PSP // Optimization. 1992. Vol. 23, No. 4. P. 357–367.

[16] 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.

[17] Dudycz S., Marcinkowski J., Paluch K., Rybicki B. 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). Springer, 2017. P. 173–185. (Lect. Notes Comput. Sci.; Vol. 10328).

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

[19] Gimadi E. Kh. Approximation efficient algorithms with performance guarantees for some hard routing problems // Proc. 2nd Int. Conf. Optimization and Applications, OPTIMA-2011 (Petrovac, Montenegro, Sertember 25 — October 2, 2011). Moscow: VC RAN, 2011. P. 98–101.

[20] 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 (Vladivostok, Russia, Sept. 19–23, 2016). Cham: Springer, 2016. P. 159–170. (Lect. Notes Comput. Sci.; Vol. 9869).

[21] Gutin G., Punnen A. P. (eds.) The Traveling Salesman Problem and its variations // Dordrecht; Boston; London: Kluwer Acad. Publ., 2002.

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

[23] Hopcroft J. E., Karp R. M. An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs // SIAM J. Comput. 1973. Vol. 2, No. 4. P. 225–231.

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

[25] 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. and Phys. Sci.; Vol. 19.).

[26] 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, August 21–23, 2009). Heidelberg: Springer, 2009. P. 298–311. (Lect. Notes Comput. Sci.; Vol. 5687).

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