Том 24, номер 3, 2017 г., Стр. 5-19

УДК 519.8
Гимади Э. Х., Цидулко О. Ю.
Асимптотически точный алгоритм для задачи нескольких коммивояжёров на случайных входных данных с дискретным распределением

Аннотация:
Рассматривается задача $m$ коммивояжёров ($m$-Peripatetic Salesman Problem) на случайных входных данных c дискретным распределением. Для её решения предлагается приближённый полиномиальный алгоритм, который при определённых ограничениях на входные данные с вероятностью, стремящейся к 1 с ростом размерности задачи, даёт точное решение задачи $m$-PSP как с одинаковыми, так и с различными весовыми функциями маршрутов коммивояжёров.
Ил. 1, библиогр. 27.

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

DOI: 10.17377/daio.2017.24.551

Гимади Эдуард Хайрутдинович ^1,2
Цидулко Оксана Юрьевна ^1,2
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: gimadi@math.nsc.ru, tsidulko.ox@gmail.com

Статья поступила 3 августа 2016 г.
Исправленный вариант — 13 октября 2016 г.

Литература

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

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

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

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

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

[6] Гимади Э. Х., Глазков Ю. В., Цидулко О. Ю. Вероятностный анализ алгоритма решения трёхиндексной $m$-слойной планарной задачи о назначениях на одноциклических подстановках // Дискрет. анализ и исслед. операций. 2014. T. 21, № 1. C. 15–29.

[7] Гимади Э. Х., Истомин А. М., Рыков И. А., Цидулко О. Ю. Вероятностный анализ приближенного алгоритма для решения задачи о нескольких коммивояжерах на случайных входных данных, неограниченных сверху // Тр. ИММ УрО РАН. 2014. Т. 20, № 2. C. 88–98.

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

[9] Гимади Э. Х., Перепелица В. А. Статистически эффективный алгоритм выделения гамильтонова контура (цикла) // Дискретный анализ. Новосибирск: Ин-т математики, 1973. Т. 22. С. 15–28.

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

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

[12] Коршунов А. Д. О мощности некоторых классов графов // Докл. АН СССР. 1970. Т. 193, № 6. С. 1230–1233.

[13] Петров В. В. Предельные теоремы для сумм независимых случайных величин. М.: Наука, 1987. 252 c.

[14] Angluin D., Valiant L. G. Fast probabilistic algorithms for Hamiltonian circuits and matchings // J. Comput. Syst. Sci. 1979. Vol. 18, No. 2. P. 155–193.

[15] Bollobás B., Fenner T. I., Frieze A. M. An algorithm for finding Hamilton paths and cycles in random graphs // Combinatorica. 1987. Vol. 7, No. 4. P. 327–341.

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

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

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

[19] De Kort J. B. J. M. A branch and bound algorithm for symmetric 2-peripatetic salesman problems // Eur. J. Oper. Res. 1993. Vol. 70, No. 2. P. 229–243.

[20] Erdös P., Rényi A. On random graphs I // Publ. Math. 1959. Vol. 6. P. 290–297.

[21] Frieze A. M. An algorithm for finding Hamilton cycles in random directed graphs // J. Algorithms. 1988. Vol. 9, No. 2. P. 181–204.

[22] Frieze A. M., Haber S. An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three // Random Struct. Algorithms. 2015. Vol. 47, No. 1. P. 73–98.

[23] Gimadi E. Kh., Glebov A. N., Skretneva A. A., Tsidulko O. Yu., Zambalaeva D. Zh. Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph // Discrete Appl. Math. 2015. Vol. 196, No. 11. P. 54–61.

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

[25] Komlós J., Szemerédi E. Limit distributions for the existence of Hamilton circuits in a random graph // Discrete Math. 1983. Vol. 43, No. 1. P. 55–63.

[26] Krarup J. The peripatetic salesman and some related unsolved problems // Combinatorial Programming: Methods and Applications. Proc. NATO Adv. Study Inst. (Versailles, France, Sept. 2–13, 1974). Dordrecht: D. Reidel, 1975. P. 173–178 (NATO Adv. Study Inst. Ser.; Vol. 19).

[27] Posa L. Hamiltonian circuits in random graphs // Discrete Math. 1976. Vol. 14, No. 4. P. 359–364.