Приближенные алгоритмы решения некоторых многоиндексных задач о назначениях
Диссертация
Рассмотрена многоиндексная аксиальная задача о назначениях. Для решения задачи предложен приближенный алгоритм, имеющий временную сложность 0(гг3). Для решения задачи на случайных входах указаны условия его асимптотической точности. Рассмотрена трехиндексная аксиальная задача о назначениях на подстановках специального вида. Исследованы случаи, когда одна подстановка является одноциклической, обе… Читать ещё >
Содержание
- 1. Приближенные алгоритмы решения многоиндексной аксиальной задачи о назначениях
- 1. 1. Многоиндексная аксиальная задача о назначениях
- 1. 1. 1. Постановка задачи
- 1. 1. 2. Нриближенный алгоритм
- 1. 2. Трехиндексные аксиальные задачи о назначениях с одной од-ноциклической подстановкой
- 1. 2. 1. Постановка задачи
- 1. 2. 2. Приближенный алгоритм
- 1. 3. Трехиндексные аксиальные задачи о назначениях с двумя од-ноциклическими подстановками
- 1. 3. 1. Постановка задачи
- 1. 3. 2. Приближенный алгоритм
- 1. 4. Трехиндексная аксиальная задача о назначениях на одноцик-лических подстановках на минимум
- 1. 4. 1. Постановка задачи
- 1. 4. 2. Приближенный алгоритм
- 1. 4. 3. Корректность работы алгоритма
- 1. 4. 4. Анализ оценок качества алгоритма
- 1. 5. Трехиндексная аксиальная задача о назначениях на одноциклических подстановках на максимум
- 1. 5. 1. Постановка задачи
- 1. 5. 2. Приближенный алгоритм
- 1. 5. 3. Анализ корректности работы и оценок качества алгоритма
- 1. 6. Разрешимость многоиндексной аксиальной задачи о назначе
- 1. 1. Многоиндексная аксиальная задача о назначениях
- 1. % ниях на одноциклических подстановках
- 1. 6. 1. Постановка задачи
- 1. 6. 2. Предварительные замечания и необходимый признак разрешимости задачи
- 1. 6. 3. Критерий разрешимости 7-индексной задачи
- 1. 6. 4. Заключительные замечания о разрешимости многоиндексной задачи
- 2. Приближенные алгоритмы решения трехиндексной планарной задачи о назначениях
- 2. 1. m-слойная планарная задача о назначениях
- 2. 1. 1. Постановка задачи
- 2. 1. 2. Приближенный алгоритм для случая т < п/
- 2. 1. 3. Анализ работы алгоритма
- 2. 2. Двухслойная планарная задача о назначениях с одной одно-циклической подстановкой
- 2. 2. 1. Постановка задачи
- 2. 2. 2. Приближенный алгоритм
- 2. 3. Двухслойная планарная задача о назначениях на одноцикли-ческих подстановках
- 2. 3. 1. Постановка задачи
- 2. 3. 2. Приближенный алгоритм
- 2. 3. 3. Постановка задачи в терминах теории графов
- 2. 3. 4. Алгоритм с оценкой точности 9/4 + 0(1/п) для метрической задачи с одинаковой весовой функцией
- 2. 3. 5. Обоснование оценок точности алгоритма. м 2.3.6 Алгоритм с оценкой точности 12/5 + 0(1 /тт.) для метрической задачи с разными весовыми функциями
- 2. 3. 7. Обоснование оценок точности алгоритма
- 2. 4. Двухслойная планарная задача о назначениях на одиоцикли-ческих подстановках на максимум
- 2. 4. 1. Постановка задачи
- 2. 4. 2. Приближенный алгоритм с константной оценкой точности 3/
- 2. 4. 3. Обоснование оценок точности алгоритма
- 2. 1. m-слойная планарная задача о назначениях
Список литературы
- Береснев В. Л., Гимади Э. X., Дементьев В. Т. Экстремальные задачи стандартизации // Новосибирск: Наука, 1978.
- Гимади Э. X. Задача коммивояжера на максимум: условие асим-тотической точности алгоритма «Иди в самый удаленный город» // Управляемые системы: Сб. науч. тр., Вып. 29, Новосибирск: Ин-т математики СО АН СССР, 1989, С. 11−15.
- Гимади Э. X., Глебов Н. И., Перепелица В. А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики, Москва: Наука, 1975, С. 35−42.
- Гимади Э. X., Перепелица В. А. К задаче нахоэ/сдения минимального гамильтонового контура на графе со взвешенными дугами // Дискретный анализ, Новосибирск, Ин-т математики СО АН СССР, 1969, Вып. 15, С. 57−65.
- Гимади Э. X., Перепелица В. А. Асимптотический подход к решению задач коммивояжера // Управляемые системы. Сб. науч. трудов, Вып. 12, Новосибирск: Ин-т математики СО АН СССР, 1974, С. 35−45.
- Гимади Э. X., Сердюков А. И. Аксиальные трехиндекспые задачи о назначении и коммивояжера: быстрые приближенные алгоритмы и их вероятностный анализ // Известия высших учебных заведений. Математика, 1999, № 12(451), С. 19−25.
- Гэри М., Джонсон Д. Вычислительные машины и труднорешае-мые задачи // М.: Мир, 1982.
- Емеличев В. А., Ковалев М. М., Кравцов М. М. Многогранники, графы, оптимизация // М: Наука, 1981.
- Коробков В. К., Кричевский Р. Е. Некоторые алгоритмы для решения задачи коммивояжера // Математические модели и методы оптимального планирования, Новосибирск, Наука, 1966.
- Кляус П. С. Обобщение тестовых задач для задачи коммивояжера // Препринт № 16, Институт математики академии наук БССР, Минск, 1976.
- Ковалев М. М., Котов В. М. Анализ алгоритмов, конструирующих гамильтонов цикл максимального веса // Вести Академии наук БССР, Серия физ-мат. наук, 1984, № 4, С. 45−50.
- Ковалев М. М., Котов В. М. Оценка ошибки серий приближенных алгоритмов // Вестник Белорусского государственного университета, Серия I, Физика, Математика, Механика, 1986, № 3, С. 44−48.
- Косточка А. В., Сердюков А. И. Полиномиальные алгоритмы с оценками 3/4 и 5/6 для задачи коммивояжера на максимум // Управляемые системы. Сб. науч. тр. Вып. 26. Новосибирск: Ин-т математики СО АН СССР, 1985, С. 54−59.
- Оре О. Теория графов // Москва, Наука, 1980.
- Сердюков А. И. О некоторых экстремальных обходах в графах // Управляемые системы. Сб. науч. тр. Вып. 17 Новосибирск: Ин-т математики СО АН СССР, 1978, С. 76−79.
- Сердюков А. И. Алгоритм с оценкой для задачи коммивояжера на максимум // Управляемые системы. Сб. науч. тр. Вып. 25. Новосибирск: Ин-т математики СО АН СССР, 1984, С. 80−86.
- Сердюков А. И. Сложность решения задачи коммивояжера с предписанием на графах с малыми степенями вершин // Управляемые системы. Сб. науч. тр. Вып. 26. Новосибирск: Ин-т математики СО АН СССР, 1985, С. 73−82.
- Сердюков А. И. Асимтотически точный алгоритм для задачи коммивояжера на максимум в евклидовом пространстве // Управляемые системы. Сб. науч. тр. Вып. 25. Новосибирск: Ин-т математики СО АН СССР, 1987, С. 79−87.
- Сердюков А. И. Задача коммивояжера на максимум в конечномерных вещественных пространствах // Дискретный анализ и исследование операций, № 1(2), 1995, С. 50−56.
- Arora S. Probabilistic checking of proofs and the hardness of approximation problems // PhD thesis, U. C. Berkeley, 1994.
- Arora S., Lund C. Hardness of approximation //In Approximation algorithms for NP-hard Problems, PWS Publishing, 1996.
- Arora S., Lund C., Motwani R., Sudan M., Szegedy M. Proof verification and hardness of approximation problems // J. Assoc. Comput. Mach., 1998, no. 45, P. 501−555.
- Arthanari T. S. On the traveling salesman problem // Communic. XI Symp. Math. Program., Bonn, 1982.
- Arthanari T. S., Usha M. An alternative formulation of the symmetric traveling salesman problem and its properties // Discrete Appl. Math., 2000, no. 98, P. 173−190.
- Arthanari T. S., Usha M. On the equivalence of multistage-insertion and cycle-shrink formulation for the symmetric traveling salesman problem // Oper. Res. Lett., 2001, no. 29, P. 129−139.
- Ascheuer N. Hamiltonian Path Problem in the On-line Optimization of Flexible Manufacturing Systems // PhD thesis, Technische Universitaet Berlin, 1995.
- Ascheuer N., Fischetti M., Groetschel M. A polyhedral study of the asymmetric traveling salesman problem with time windows // Networks, 1995, no. 36, P. 69−79.
- Ascheuer N., Juenger M., Reinelt G. A branch and cut algorithm for the asymmetric traveling salesman problem with precedence constraints // Comput. Optim. Appl., 2000, no. 17, P. 61−84.
- Baki M. F. Solvable cases of the traveling salesman problem // Oper. Res., 1964, no. 12, P. 665−679.
- Baki M. F., Kabadi S. N. A note of recognition of Dernidenko matrices 11 Working paper, Department of Management Sciences, University of Waterloo, 1997.
- Balas E., Fischetti M. On the monotonization of polyhedra // Math. Program. Ser. A, 1997, no. 78, P. 59−84.
- Balas E., Toth P. Branch and Bound Methods //In The traveling Salesman Problem: Guide Tour of Combinatorial Optimization, Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G. Shmoys D. B., eds., Wiley, Chichester, 1985, P. 361−401.
- Balas E., Saltzman M. J. Facets of the three-index assignment polytope 11 Discrete Appl. Math., 1989, V. 23, no.3, P. 201−229.
- Balas E., Saltzman M. J. An algorithm for the three-index assignment problem // Oper. Res., 1991, V. 39, no. l, P. 150−161.
- Ball M., Magazine M. Sequencing of insertion in printed circuit board assembly // MBA thesis, Faculty of Administration, University of New Brunswick, Canada, 1995.
- Beloni A., Lucena A. A relax and cut algorithm for the traveling salesman problem // Technical report, Laboratorio de Metodos Quantitativos, Departamento de Administracao, Universidade Federal do Rio de Janeiro, 2000.
- Bock F. Mathematical programming solution of traveling salesman examples // Recent Advances in Mathematical Programming, McGraw-Hill, New York, 1963.
- Burdyuk V. Y., Trofimov V. N. Generalization of the results of Gilmore and Gomory on the solution of the traveling salesman problem 11 Engg. Cybernetics, 1976, no. 11, P. 12−18.
- Burkard R. E., Cela E. Linear assignment problem and extensions // Optimierung und Controlle, Karl-Franzens-Universitaet Gras and Technische Universitaet Graz, 1998.
- Burkard R. E., Cela E., Pardalos P. M., Pitsoulis L. S.
- The quadratic assignment problem // Optimierung und Controlle, Karl-Franzens-Universitaet Gras and Technische Universitaet Graz, 1998.
- Burkard R. E., Froehlich K., Sigal I. Kh. Some remarks on 3-dimensional assignment problem // Methods of Operations Research, 1980, no.36, R 31−36.
- Burkard R. E., Klinz F., Rudolf R. Perspective of Monge properties in optimization // Discrete Appl. Math., 1996, no. 70, P. 95−96.
- Burkard R. E., Rudolf R., Woeginger G. J. Computational investigation on 3-dimensional axial assignment problems // Belgian J. of Oper. Res., 1993, no. 32, P. 85−98.
- Burkard R. E., Rudolf R., Woeginger G. J. Tree dimensional axial assignment problems with decomposable cost coefficients // Discrete Appl. Math., 1996, no. 65, P. 123−169.
- Camerini P. M., Flatta L., Maffioli F. A note of finding optimum branching // Networks, 1979, no. 9, P. 309−312.
- Carpaneto G., Toth P. Some new branching and bounding criteria for the asymmetric traveling salesman problem ]] Manafe. Sci., 1980, no. 26, P. 736−743.
- Carpaneto G., Toth P. Solution of the assignment problem // ACM Transactions on Math. Software, 1980, no. 6, P. 104−111.
- Carr R. D. Polynomial separation procedures and facet determination for inequalities of the traveling salesman polytope // PhD thesis, Department of Mathematics, Carnegie Mellon University, 1995.
- Chandrasekaran R. Recognition of Gilmore-Gomore traveling salesman problem // Discrete Appl. Math., 1986, no. 28, P. 2133−2149.
- Chekuri C., Goldberg A., Kaeger D., Levine M., Stein C.
- Experimental study of minimum cut algorithms j/ Proc. 8th ACM-SIAM Symp. Discrete Algorithms (SODA'97), 1997, P. 324−333.
- Christofides N. Worst-case analysis of a new heuristic for the traveling salesman problem // Technical Report CS-93−13, Carnegie Mellon University, 1976.
- Chvatal V. Edmonds polytopes and weakly hamiltonian graphs // Math. Program., 1973, no. 5, P. 29−40.
- Cook W. J., Cunnunghan W. H., Pulleyblank W. R., Schrijver
- A. Combinatorial Optimization j j John Wiley and Sons, New York, 1998.
- Cornuejols G., Fonlupt J., Naddef D. The traveling salesman problem on a graph and some related polyhedra // Math. Program., 1985, no. 33, P. 1−27.
- Crama Y., Spieksma F. C. R. Approximation algorithms for three-dimensional assignment problems with triangle inequalities // European J. of Oper. Res., 1992, no. 60, P. 273−279.
- Cunningham W. H., Wang Y. Restricted 2-factor polytopes // Math. Program. Ser. A, 2000, no. 87, P. 87−111.
- Dantzig G. B., Fulkerson D. R., Jonson S. M. Solution of a large scale traveling salesman problem // Oper. Res., 1954, no. 2, P. 393−410.
- Deineko V. G., Rudolf R., Woeginger R. E. On the recognition of permuted Supnick and incomplete Monge matrices // Acta Inform., 1996, no. 33, P. 559−569.
- Deineko V. G., Rudolf R., Woeginger R. E. Sometimes traveling is easy: the master tour problem // SIAM J. Discrete Math., 1998, no. 11, P. 81−93.
- Edmonds E. Path, trees and flowers // Can. J. Math., 1965, no. 17, P. 449−467.
- Edmonds E. Matching and a polyhedron with 0,1 vertices //J. Res. N. B. S. B, 1965, no. 69, P. 125−130.
- Edmonds E. Optimum branchings //J. Res. Natl. Bur. Stand., Sect. B, 1967, no. 71B, P. 233−240.
- Fischetti M. An improved bound for the asymmetric traveling salesman problem // Ricerca Operativa, 1986, no. 37, P. 71−85.
- Fischetti M., Toth P. An additive bounding procedure for combinatorial optimization problem // Oper. Res., 1989, no. 37, P. 319−328.
- Fischetti M., Toth P. An additive bounding procedure for asymmetric traveling salesman problem // Math. Program. Ser. A, 1992, no. 53, P. 173−197.
- Fisher M. L. Worst-case analysis of algorithms // Management Science, 1980, no. 26, P. 1−18.
- Fisher M. L., Nemhauser G. L., Wolsey L. A. An analysis of approximations for finding a maximum weight hamiltonian circuit / / Oper. Res., 1979, no. 27(4), P. 799−809.
- Flood M. M. The traveling-salesman problem // Oper. Res., 1956, no. 4, P. 61−75.
- Fleischmann B. A new class of cutting planes of the symmetric traveling salesman problem // Math. Program. Ser. A, 1988, no. 40, P. 225−246.
- Fon-Der-Flaass D. G. Array of distinkt representatives a very simple NP-hard problem // Discrete Mathematics, 1997, no. 171, P. 225−298.
- Frieze A. M. Complexity of a 3-dimensional assignment problem // European J. of Oper. Res., 1983, no. 13, P. 161−164.
- Frieze A. M., Yadegar L. An algorithm for solving 3-dimensional assignment problems with application to scheduling in a teaching practice // J. of the Oper. Res. Society, 1981, no. 32, P. 989−995.
- Gabov H. ~N.An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems // In Proceedings of the 15th annual ACM symposium on theory of computing (Boston, Apr. 2527), 1983, ACM, New York, P. 448−456.
- Garey M. R., Johnson D. S. Computers and Intractability. // San Francisco: W.H. Freeman and Company, 1979.
- Ghosh A. P. Expected travel among random points // Bulletin Culcatta Stat. Assoc., 1948, no. 2, P. 83−87.
- Gilmori P. C., Gomory R. E. Sequencing a one tstate-variable machine: A solvable case of the traveling salesman problem // Oper. Res., 1964, no. 12, P. 665−679.
- Gilmori P. C., Lawler E. L., Shmoys D. B. Well-solved special cases //In The traveling salesman problem: a guided tour of combinatorial
- Optimization, Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G. Shrrioys ^ D. B., eds., Wiley, Chichester, 1985, R 87−143.
- Glover F. Ejection chains, reference structures and alternating path methods for traveling salesman problem // Discrete Appl. Math., 1996, no. 65, R 223−253.
- Glover F. Finding a best traveling salesman 4~opt move in the same time as a best 2-opt move // J. Heuristics, 1996, no. 2(2), R 169−179.
- Glover F., Laguna M. Tabu Search // Kluwer, Boston, 1997.
- Goemans M. Worst-case comparison of valid inequalities for the TSP // Math. Program. Ser. A, 1995, no. 69, P. 335−349.
- Graham R. E. Bounds for Certain Multiprocessing Anomalies // Bell System Technical J., 1966, no. 45, P. 1563−1581.
- Groetschel M., Padberg M. W. On the symmetric traveling salesman problem I: inequalities // Math. Program., 1979, no. 16, P. 265−280.
- Groetschel M., Padberg M. W. On the symmetric traveling salesman problem II: lifting theorem and facets // Math. Program., 1979, no. 16, P. 281−302.
- Groetschel M., Pulleyblank W. Clique tree inequalities and the symmetric traveling salesman problem // Math. Oper. Res., 1986, no. 11, P. 537−569.
- Gutin G. and Punnen A. P. (Eds.) The traveling salesman problem and its variations // Dordrecht, Boston, London: Kluwer Ac. Publishers, 2002.
- Hansen P., Kaufman L. A primal-dual algorithm for the three-dimensional assignment problems // Cahiers du Cero, 1973, no. 15, P. 327−336.
- Hassin R., Rubinstein S. An approximation algorithm for the maximum traveling salesman problem // Inform. Process. Lett., 1998, no. 67, P. 125 130.
- Held M., Karp R. M. A Dynamic Programming Approach to Sequencing Problem // J. SIAM, 1962, no. 10(1), P. 196−210.
- Held M., Karp R. M. The traveling salesman problem and minimal spanning trees // Oper. Res., 1970, no. 18, P. 1138−1162.
- Held M., Karp R. M. The traveling salesman problem and minimum spanning trees: part II // Math. Program., 1971, no. 1, P. 6−25.
- Helsgaun K. An effective implementation of the Lon-Kernighan traveling salesman heuristic // Eur. J. Oper. Res., 2000, no. 12, P. 106−130.
- Hopcroft J. E., Karp R. M. An n5/2 algorithm for maximum matchings in bipartite graphs // SIAM J. on Computings, 1973, no. 2, P. 225−231.
- Johnson D. S. Approximation algorithms for combinatorial problems // Journal of Computing and System Science, 1974, no. 9, P. 256−278.
- Kabadi S. N. Solution of a large scale traveling salesman problem // Oper. Res., 1954, no. 2, P. 393−410.
- Kabadi S. N., Baki M. F. Gilmore-Gomory type traveling salesman problem // Comput. Oper. Res., 1999, no. 26, P. 329−351.
- Karp R. M. Reducibility among combinatorial problem //In Complexity of Computer Computation, Miller R. E. and Thatcher J. W., eds., Plenum Press, New York, 1972, P. 85−103.
- Kosaraju S. R., Park J. K., Stein C. Long tour and short superstrings // In Proc. 35rh Ann IEEE Symp. Found. Comput. Sci. (FOCS'94), 1994, P. 166−177.
- Kurzberg J. M. On approximation methods for assignment problem // Journal of the ACM, 1962, no. 9, P. 419−439.
- Land A. H., Doig A. G. An automatic methods of solving discrete programming problems // Econometrica, 1960, V. 28, no. 3.
- Lawer E. L. Combinatorial optimization: Natworks and Matroids // Holt, Rinehart and Wintson, New York, 1976.
- Lawer E. L., Lenstra J. K., Rinooy Kan A. H. G., Shmoys
- D. B. Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization // Wiley, Chichester, 1985.
- Lin S., Kernighan B. W. An effective heuristic algorithm for the traveling salesman problem // Oper. Res., 1973, no. 21, P. 972−989.
- Machol R. E. An application of the assignment problem // Oper. Res., 1970, no. 18, P. 745−746.
- Magos D. Tabu search for the planar three-index assignment problem // J. of Global Optimization, 1996, no. 8, P. 35−48.
- Magos D., Miliotis An algorithm for the planar three-index assignment problem // European J. of Oper. Res., 1994, no. 77, P. 141−153.
- Marks E. S. A lower bound for the expected travel among m random points // Ann. Math. Stat., 1948, no. 19, P. 419−422.
- Melamed I. I., Sergeev S. I., Sigal I. Kh. The traveling salesman problem -I. Theoretical issue // Automat. Remote controle, 1989, P. 11 471 173.
- Melamed I. I., Sergeev S. I., Sigal I. Kh. The traveling salesman problem. Exact Algorithms // Automat. Remote controle, 1990, P. 14 591 479.
- Menger K. Das Botenproblem // Ergebniss Eines Mathematischen Kolloquiums, 1932, no. 2, P. 11−12.
- Miller D. L., Pekny J. F. Results from a parallel branch and bound algorithm for the asymmetric traveling salesman problem // Oper. Res. Lett., 1989, no. 8, P. 129−135.
- Miller D. L., Pekny J. F. Exact solution of large asymmetric traveling salesman problems // Science, 1991, no. 251, P. 754−761.
- Mitchell J. S. B. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems // SIAM J. Comput., 1999, no. 28, P. 1298−1309.
- Morton G., Land A. H. A contribution to the «Traveling-Salesman «problem // J.D. Stat. Soc., Ser. B, 1955, no. 17, P. 185−203.
- Naddef D., Rinalde G. The symmetric traveling salesman problem polytope and its graphical relaxation: Composition of valid inequalities // Math. Program. Ser. A, 1991, no. 51, P. 359−400.
- Naddef D., Rinalde G. The crown inequalities for the traveling salesman polytope // Math. Oper. Res., 1992, no. 17, P. 308−326.
- Naddef D., Rinalde G. The graphical relaxation: a new framework for the symmetric traveling salesman polytope // Math. Program. Ser. A, 1993, no. 58, P. 53−88.
- Naddef D., Rinalde G. The symmetric traveling salesman polytope: New facets from the graphical relaxation // Technical report, Laboratoire ID-IMAG, 2000.
- Padberg M. W., Rinalde G. An efficient algorithm for the minimum capacity cut problem // Math. Program. Ser. A, 1990, no. 47, P. 19−36.
- Padberg M. W., Sung T. Y. An analytical comparison of different formulations of the traveling salesman problem // Math. Program. Ser. A, 1991, no. 52, P. 315−357.
- Papadimitriu C. H., Yannakakis M. Optimization, approximation, and complexity classes // Journal of Computer and System Sciences, 1991, V. 43, P. 425−440.
- Park J. K. A special case of the n-vertex traveling salesman problem that can be solved in 0(n) time // Inform. Process., 1991, no. 25, P. 247−254.
- Pierskalla W. P. The tri-substitution method for the three-multidimensional problem // Canadian ORS Journal, 1997, no.-5, P. 71−81.
- Pierskalla W. P. The multidimensional assignment problem // Oper. Res., 1968, no. 16, P. 422−431.127. f
- Poore A. B., Robertson III A. J. A new Lagrangian relaxation based algorithm for a class of multidimensional assignment problems // Computational Optimization and Applications, 1997, no. 8, P. 129−150.
- Punnen A. P., Glover F. Implementing ejection chains with combinatorial leverage for the TSP J/ Research Report, University of Colorado-boulder, 1996.
- Rego C. Relaxed tours and path ejection for the traveling salesman problem 11 Eur. J. Oper. Res., 1998, no. 106, P. 522−538.
- Reineld G. The Traveling Salesman: Computational Solutions for TSP Applications // Springer-Verlag, Berlin, 1994.
- Rinnoy Kan A. H. G. An introduction to the analysis of approximation algorithms // Discrete Appl. Math., 1986, no. 14, P. 171−186.
- Robinson J. B. On the Hamiltonian game: a traveling salesman problem II Theoretical report, RAND Research Memorandum RM-303, 1949.
- Sahni S. General technique for combinatorial approximation // Oper. Res., 1969, no. 14, P. 1005−1016.
- Sahni S., Gonzales T. P. P-Complete Approximation Problem // Assoc. Comput. Mach., 1976, V. 23, no. 3, P. 555−565.
- Shmoys D. Computing near-optimal solutions to combinatorial optimization problem // Comutiong, 1982, no. 28, P. 257−267.
- Slominski D. Computing near-optimal solutions to combinatorial optimization problem //In Advances in Combinatorial Optimization, Cook W., Lovasz L., Seymour P., eds., Ams, Providence RI, 1995, P. 335−397.
- Tarjan R. E. Finding optimum branchings // Networks, 1977, no. 7, P. 25−35.
- Trevisan L. When Hamming meets Euclid: the approximability of geometric TSP and MST //In Proc. 29th ACM Symp. Theory Comput., 1997, P. 27−39.
- Vlach M. Branch and bound method for the three-index assignment problem // Ekonomicko-Matematicky Obzor, 1967, no. 12, P. 181−191.
- Wolsey L. A. Integer Programming // Wiley, Chichester, 1998.