×

zbMATH — the first resource for mathematics

An analysis of the extended Christofides heuristic for the \(k\)-depot TSP. (English) Zbl 1219.90149
Summary: We study an extension of the classical traveling salesman problem (TSP) to a situation with \(k\geq 2\) depots at each of which a distinct salesman is based. We show that a non-trivial extension of the well-known Christofides heuristic has a tight approximation ratio of \(2 - 1/k\), which improves on the known 2-approximation algorithm from the literature.

MSC:
90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arkin, E.M.; Hassin, R.; Levin, A., Approximations for minimum and min – max vehicle routing problems, Journal of algorithms, 59, 1, 1-18, (2006) · Zbl 1112.68135
[2] P.R. Chandler, M. Pachter, Research issues in autonomous control of tactical UAVs, in: Proceedings of American Control Conference, 1998, pp. 394-398.
[3] P.R. Chandler, M. Pachter, D. Swaroop, J.M. Fowler, J.K. Howlett, S. Rasmussen, C. Schumacher, K. Nygard, Complexity in UAV cooperative control, in: Proceedings of American Control Conference, 2002, pp. 1831-1836.
[4] N. Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, 1976.
[5] Eiselt, H.A.; Gendreau, M.; Laporte, G., Arc routing problems, part i: the Chinese postman problem, Operations research, 43, 2, 231-242, (1995) · Zbl 0837.90037
[6] Foulds, L.R.; Wilson, J.M., A variation of the generalized assignment problem arising in the New Zealand dairy industry, Annals of operations research, 69, 105-114, (1997) · Zbl 0880.90035
[7] Garey, Michael R.; Johnson, David S., Computers and intractability: A guide to the theory of NP-completeness, (1979), WH Freeman & Co. New York, USA · Zbl 0411.68039
[8] Giosa, I.D.; Tansini, I.L.; Viera, I.O., New assignment algorithms for the multi-depot vehicle routing problem, Journal of the operational research society, 53, 9, 977-984, (2002) · Zbl 1079.90030
[9] Korte, B.H.; Vygen, J., Combinatorial optimization: theory and algorithms, (2008), Springer Verlag · Zbl 1149.90126
[10] Malik, W.; Rathinam, S.; Darbha, S., An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem, Operations research letters, 35, 6, 747-753, (2007) · Zbl 1169.90436
[11] Papadimitriou, C.H.; Steiglitz, K., Approximation algorithms for the traveling salesman problem, (), 410-419
[12] S. Rathinam, R. Sengupta, 3/2-approximation algorithm for a generalized, multiple depot, Hamiltonian path problem, Technical Report, University of California, Berkeley, 2007. · Zbl 1182.90074
[13] S. Rathinam, R. Sengupta, 5/3-approximation algorithm for a multiple depot, terminal Hamiltonian path problem, Technical Report, University of California, Berkeley, 2007. · Zbl 1182.90074
[14] Rathinam, S.; Sengupta, R., 3/2-approximation algorithm for two variants of a 2-depot Hamiltonian path problem, Operations research letters, 38, 1, 63-68, (2010) · Zbl 1182.90074
[15] Rathinam, S.; Sengupta, R.; Darbha, S., A resource allocation algorithm for multi-vehicle systems with non holonomic constraints, IEEE transactions on automation science and engineering, 4, 1, 98-104, (2006)
[16] Renaud, J.; Laporte, G.; Boctor, F.F., A tabu search heuristic for the multi-depot vehicle routing problem, Computers and operations research, 23, 3, 229-235, (1996) · Zbl 0855.90055
[17] Rosenkrantz, D.J.; Stearns, R.E.; Lewis, P.M., An analysis of several heuristics for the traveling salesman problem, SIAM journal on computing, 6, 563-581, (1977) · Zbl 0364.90104
[18] Yadlapalli, S.; Malik, W.; Darbha, S.; Pachter, M., A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem, Nonlinear analysis. real world applications, 10, 4, 1990-1999, (2009) · Zbl 1163.90722
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.