EN|RU
Свободный доступ к полным текстам предоставляется после 1 июля года, следующего за годом публикации. Полный текст этой статьи можно приобрести на сайте elibrary.ru.

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2017, 11:3, 354-361

Том 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.

 © Институт математики им. С. Л. Соболева, 2015