Том 20, номер 5, 2013 г., Стр. 13-30

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

Аннотация:
Рассматривается частный случай задачи отыскания $m$ гамильтоновых циклов с ограничениями на число повторений рёбер ($m$-Capacitated Peripatetic Salesman Problem, $m$-$\mathrm{CPSP}$) – задачи $2$-$\mathrm{CPSP}$ на минимум и максимум с весами рёбер из целочисленного сегмента $\{1,q\}$. Пропускные способности рёбер заданы независимыми случайными величинами, принимающими значение $2(1)$ с вероятностью $p(1-p)$. Построены алгоритмы решения задач $2$-$\mathrm{CPSP_{min}}$ и $2$-$\mathrm{CPSP_{max}}$ с гарантированными оценками точности в среднем по всем возможным входам. В частности, для задач на графах с весами рёбер $1$ и $2$ алгоритмы имеют оценки точности $(19-5p)/12$ и $(25+7p)/36$ в среднем по всем возможным входам для задачи на минимум и на максимум соответственно.
Ил. 17, библиогр. 20.

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

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

Статья поступила 27 декабря 2012 г.
Исправленный вариант — 10 июня 2013 г.

Литература

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

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

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

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

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

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

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

[8] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. - М.: Мир, 1982. - 416 c.

[9] Baburin A. E., Della Croce F., Gimadi E. K., Glazkov Yu. V., Paschos V. Th. Approximation algorithms for the 2-PSP with edge weights 1 and 2 // Discrete Appl. Math. - 2009. - Vol. 157, N 9. - P. 1988–1992.

[10] Berman P., Karpinski M. 8/7-Approximation algorithm for (1,2)-TSP // Proc. 17th Annual ACM-SIAM Symp. Discrete Algorithm (SODA’06) (Miami, January, 2006). - New York: ACM, 2006. - P. 641–648.

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

[12] Gutin G., Punnen A. P. (eds.) The traveling salesman problem and its variations. - Dordrecht; Boston; London: Kluwer Acad. Publ., 2002. - 830 p.

[13] Della Croce F., Paschos V. Th., Wolfler Calvo R. Approximating the 2-peripatetic traveling salesman problem // 7th Workshop Modeling and Algorithms for Planning and Scheduling Problems, MAPSP 2005 (Siena, Italy, June 6–10, 2005). - Berlin: Springer-Verl., 2005. - P. 114–116.

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

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

[16] Duchenne É., Laporte G., Semet F. The undirected m-capacitated peripatetic salesman problem. // Eur. J. Oper. Res. - 2012. - Vol. 223, N 3. - P. 637–643.

[17] Krarup J. The peripatetic salesman and some related unsolved problems // Combinatorial programming: methods and applications (Proc. NATO Advanced Study Inst., Versailles, 1974). - 1975. - P. 173–178.

[18] Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B. (eds.) The traveling salesman problem: a guided tour of combinatorial optimization. - Chichester; New York; Brisbane; Toronto; Singapore: John Wiley& Sons, 1985. - 463 p.

[19] Papadimitriu C. H., Yannakakis M. The travelling salesman problem with distances one and two // Math. Oper. Res. - 1993. - Vol. 18, N 1. - P. 1–11.

[20] Roskind J., Tarjan R. E. A note on finding minimum-cost edge-disjoint spanning trees // Math. Oper. Res. - 1985. - Vol. 10, N 4. - P. 701–708.