×
Westerlund, Andreas; Göthe-Lundgren, Maud; Larsson, Torbjörn

A note on relatives to the Held and Karp 1-tree problem. (English) Zbl 1113.90165

Oper. Res. Lett. 34, No. 3, 275-282 (2006).
Summary: We study a class of graph problems which includes as special cases the Held and Karp 1-tree problem, and the minimum spanning tree problem with one degree constraint studied by Glover and Klingman. For another special case, we note a mistake in a paper by Ramesh, Yoon and Karwan.

Cited in 3 Documents

MSC:

90C35 Programming involving graphs or networks
05C85 Graph algorithms (graph-theoretic aspects)
90C27 Combinatorial optimization

Keywords:

1-tree problem; degree constraint; counter-example; polynomial time-complexity; vehicle routing; traveling salesman

Software:

VRP
Cite Review PDF
Full Text: DOI

References:

[1] Beasley, J. E., An SST-based algorithm for the Steiner problem in graphs, Networks, 19, 1-16 (1989) · Zbl 0662.90083
[2] Carr, R.; Vempala, S., On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems, Math. Programming Ser. A, 100, 569-587 (2004) · Zbl 1136.90031
[3] Christofides, N., The travelling salesman problem, (Christofides, N.; Mingozzi, A.; Toth, P.; Sandi, C., Combinatorial Optimization (1979), Wiley: Wiley Chischester), 131-149 · Zbl 0506.90059
[4] Fischetti, M.; Toth, P., An additive approach for the optimal solution of the prize-collection travelling salesman problem, (Golden, B. L.; Assad, A. A., Vehicle Routing (1988), Elsevier: Elsevier North-Holland), 319-343 · Zbl 0686.90029
[5] Fischetti, M.; Toth, P., An efficient algorithm for the min-sum arborescence problem on complete digraphs’, ORSA J. Comput., 5, 4, 426-434 (1993) · Zbl 0789.90082
[6] Fisher, M., Optimal solution of vehicle routing problems using minimum \(k\)-trees, Oper. Res., 42, 626-642 (1994) · Zbl 0815.90066
[7] Fisher, M., A polynomial algorithm for the degree-constrained minimum \(k\)-tree problem, Oper. Res., 42, 775-779 (1994) · Zbl 0815.90131
[8] Gabow, H., A good algorithm for smallest spanning trees with a degree constraint, Networks, 8, 201-208 (1978) · Zbl 0384.90105
[9] B. Gavish, K. Srikanth, Efficient branch and bound code for solving large scale traveling salesman problems to optimality, Working paper QM8329 Graduate School of Management University of Rochester, NY, 1983.; B. Gavish, K. Srikanth, Efficient branch and bound code for solving large scale traveling salesman problems to optimality, Working paper QM8329 Graduate School of Management University of Rochester, NY, 1983.
[10] Gavish, B.; Srikanth, K., An optimal solution method for large-scale multiple traveling salesman problems, Oper. Res., 34, 698-717 (1986) · Zbl 0612.90099
[11] Glover, F.; Klingman, D., Finding minimum spanning trees with fixed number of links at a node, (Roy, B., Combinatorial Programming: Methods and Applications (1975), D. Reidel Publishing: D. Reidel Publishing Dordrecht, Holland), 191-201 · Zbl 0395.90077
[12] Goemans, M.; Bertsimas, D., Probabilistic analysis for the euclidean traveling salesman problem, Math. Oper. Res., 16, 72-89 (1991) · Zbl 0733.90072
[13] Göthe-Lundgren, M.; Jörnsten, K.; Värbrand, P., On the nucleolus of the basic vehicle routing game, Math. Programming, 72, 83-100 (1996) · Zbl 0851.90031
[14] Held, M.; Karp, R. M., The traveling-salesman problem and minimum spanning trees, Oper. Res., 18, 1138-1162 (1970) · Zbl 0226.90047
[15] Kataoka, S.; Yamada, T.; Morito, S., Minimum directed 1-subtree relaxation for score orienteering problem, Europ. J. Oper. Res., 104, 139-153 (1998) · Zbl 0955.90108
[16] Leclerc, M.; Rendl, F., Constrained spanning trees and the traveling saleman problem, Europ. J. Oper. Res., 39, 96-102 (1989) · Zbl 0679.90085
[17] Martinhon, C.; Lucena, A.; Maculan, N., Stronger \(K\)-tree relaxations for the vehicle routing problem, Europ. J. Oper. Res., 158, 56-71 (2004) · Zbl 1061.90023
[18] Ramesh, R.; Yoon, Y.; Karwan, M., An optimal algorithm for the orienteering tour problem, ORSA J. Comput., 4, 155-165 (1992) · Zbl 0782.90093
[19] Shutler, P., An improved branching rule for the symmetric travelling salesman problem, J. Oper. Res. Soc., 52, 169-175 (2001) · Zbl 1131.90444
[20] Smith, T.; Thompson, G., A LIFO implicit enumeration search algorithm for the symmetric traveling salesman problem using Held and Karp’s 1-tree relaxation, Ann. Discrete Appl. Math., 1, 479-493 (1977) · Zbl 0368.90109
[21] K. Srikanth, An improved algorithm for computing degree-constrained minimal spanning trees, Technical report Graduate School of Management University of Rochester, 1980.; K. Srikanth, An improved algorithm for computing degree-constrained minimal spanning trees, Technical report Graduate School of Management University of Rochester, 1980.
[22] K. Srikanth, Travelling salesman problems and related routing problems, Ph.D. Thesis, University of Rochester, 1984.; K. Srikanth, Travelling salesman problems and related routing problems, Ph.D. Thesis, University of Rochester, 1984.
[23] Valenzuela, C.; Jones, A., Estimating the Held-Karp lower bound for the geometric tsp, Europ. J. Oper. Res., 102, 157-175 (1997) · Zbl 0948.90034
[24] Volgenant, T.; Jonker, R., A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation, Europ. J. Oper. Res., 9, 83-89 (1982) · Zbl 0471.90088
[25] Volgenant, T.; Jonker, R., The symmetric traveling salesman problem and edge exchanges in minimal 1-trees, Europ. J. Oper. Res., 12, 394-403 (1983) · Zbl 0496.90079
[26] A. Westerlund, Decomposition schemes for the traveling salesman subtour problem, Licentiate Thesis LiU-TEK-LIC-2002:939, Division of Optimization, Department of Mathematics, Linköping University, Sweden, 2002.; A. Westerlund, Decomposition schemes for the traveling salesman subtour problem, Licentiate Thesis LiU-TEK-LIC-2002:939, Division of Optimization, Department of Mathematics, Linköping University, Sweden, 2002.
[27] A. Westerlund, M. Göthe-Lundgren, T. Larsson, A stabilized column generation scheme for the traveling salesman subtour problem, Revised for publication in Discrete Appl. Math.; A. Westerlund, M. Göthe-Lundgren, T. Larsson, A stabilized column generation scheme for the traveling salesman subtour problem, Revised for publication in Discrete Appl. Math. · Zbl 1111.90097
[28] Yamamoto, Y., The Held-Karp algorithm and degree-constrained minimum 1-trees, Math. Programming, 15, 228-231 (1978) · Zbl 0387.90097
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.