research-article

Reoptimization of minimum and maximum traveling salesman's tours

Authors:

Giorgio Ausiello,

Bruno Escoffier,

Jérôme Monnot,

Vangelis PaschosAuthors Info & Claims

Journal of Discrete Algorithms, Volume 7, Issue 4

Pages 453 - 463

https://doi.org/10.1016/j.jda.2008.12.001

Published: 01 December 2009 Publication History

Abstract

In this paper, reoptimization versions of the traveling salesman problem (TSP) are addressed. Assume that an optimum solution of an instance is given and the goal is to determine if one can maintain a good solution when the instance is subject to minor modifications. We study the case where nodes are inserted in, or deleted from, the graph. When inserting a node, we show that the reoptimization problem for MinTSP is approximable within ratio 4/3 if the distance matrix is metric. We show that, dealing with metric MaxTSP, a simple heuristic is asymptotically optimum when a constant number of nodes are inserted. In the general case, we propose a 4/5-approximation algorithm for the reoptimization version of MaxTSP.

References

[1]

Archetti, C., Bertazzi, L. and Speranza, M.G., Reoptimizing the traveling salesman problem. Networks. v42 i3. 154-159.

[2]

G. Ausiello, V. Bonifaci, B. Escoffier, Complexity and approximation in reoptimization, in: Cahier du LAMSADE 281, LAMSADE, Université Paris-Dauphine, 2008

[3]

Bartusch, M., Möhring, R.H. and Radermacher, F.J., Scheduling project networks with resource constraints and time windows. Ann. Oper. Res. v16. 201-240.

Digital Library

[4]

Bartusch, M., Möhring, R.H. and Radermacher, F.J., A conceptional outline of a dss for scheduling problems in the building industry. Decision Support Syst. v5. 321-344.

[5]

Bilò, D., Böckenhauer, H.-J., Hromkovic, J., Královic, R., Mömke, T., Widmayer, P. and Zych, A., Reoptimization of Steiner trees. In: Gudmundsson, J. (Ed.), Lecture Notes in Computer Science, vol. 5124. Springer. pp. 258-269.

Digital Library

[6]

H.-J. Böckenhauer, L. Forlizzi, J. Hromkovic, J. Kneis, J. Kupke, G. Proietti, P. Widmayer, Reusing optimal tsp solutions for locally modified input instances, in: 4th IFIP Int. Conf. on Theoretical Computer Science, 2006, pp. 251-270

[7]

Chen, Z.-Z., Okamoto, Y. and Wang, L., Improved deterministic approximation algorithms for Max TSP. Inform. Process. Lett. v95. 333-342.

Digital Library

[8]

N. Christofides, Worst-case analysis of a new heuristic for the traveling salesman problem, Technical Report 338, Grad School of Industrial Administration, Canergie-Mellon University, Pittsburgh, 1976

[9]

Eppstein, D., Galil, Z., Italiano, G.F. and Nissenzweig, A., Sparsification - a technique for speeding up dynamic graph algorithms. J. ACM. v44 i5. 669-696.

Digital Library

[10]

B. Escoffier, M. Milanic, V.T. Paschos, Simple and fast reoptimizations for the Steiner tree problem, in: Cahier du LAMSADE 245, LAMSADE, Université Paris-Dauphine, 2007

[11]

Garey, M.R. and Johnson, D.S., Computer and Intractability: A Guide to the Theory of NP-Completeness. 1979. W. H. Freeman.

Digital Library

[12]

Gutin, G. and Punnen, A.P., The Traveling Salesman Problem and Its Variations. 2002. Combinatorial Optimization, 2002.Kluwer Academic Publishers.

[13]

D. Hartvigsen, Extensions of matching theory, PhD thesis, Carnegie-Mellon University, 1984

[14]

Hassin, R. and Rubinstein, S., A 7/8-approximation algorithm for metric Max TSP. Inform. Process. Lett. v81 i5. 247-251.

Digital Library

[15]

Henzinger, M.R. and King, V., Maintaining minimum spanning trees in dynamic graphs. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (Eds.), Lecture Notes in Computer Science, vol. 1256. Springer. pp. 594-604.

Digital Library

[16]

Johnson, D.S. and McGeoch, L.A., The traveling salesman problem: a case study. In: Aarts, E., Lenstra, J.K. (Eds.), Local Search in Combinatorial Optimization, Wiley.

[17]

Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. and Shmoys, D.B., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. 1985. Discrete Mathematics and Optimization, 1985.Wiley.

[18]

C.H. Papadimitriou, K. Steiglitz, Some complexity results for the traveling salesman problem, in: STOC'76, 1976, pp. 1-9

Digital Library

[19]

Papadimitriou, C.H. and Yannakakis, M., The traveling salesman problem with distances one and two. Math. Oper. Res. v18. 1-11.

[20]

Rosenkrantz, D.J., Stearns, R.E. and Lewis II, P.M., An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. v6 i3. 563-581.

[21]

Sahni, S. and Gonzalez, T.F., P-complete approximation problems. J. ACM. v23 i3. 555-565.

Digital Library

[22]

Schäffter, M.W., Scheduling with forbidden sets. Discrete Appl. Math. v72 i1-2. 155-166.

Digital Library

[23]

Serdyukov, A.I., An algorithm with an estimate for the traveling salesman problem of the maximum. Upravlyaemye Sistemy. v25. 80-86.

[24]

A. Zych, D. Bilò, P. Widmayer, Reoptimization of weighted graph and covering problems, in: WAOA, 2008, in press

Cited By

Bilò D(2024)New Algorithms for Steiner Tree ReoptimizationAlgorithmica10.1007/s00453-024-01243-286:8(2652-2675)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s00453-024-01243-2
Goyal KMömke T(2020)Robust Reoptimization of Steiner TreesAlgorithmica10.1007/s00453-020-00682-x82:7(1966-1988)Online publication date: 1-Jul-2020
https://dl.acm.org/doi/10.1007/s00453-020-00682-x
Dai WYang Y(2019)Reoptimization of minimum latency problem revisitedJournal of Combinatorial Optimization10.1007/s10878-018-0317-337:2(601-619)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s10878-018-0317-3
Show More Cited By

Reoptimization of minimum and maximum traveling salesman's tours

Recommendations

Reoptimization of minimum and maximum traveling salesman's tours
SWAT'06: Proceedings of the 10th Scandinavian conference on Algorithm Theory

In this paper, reoptimization versions of the traveling salesman problem (TSP) are addressed. Assume that an optimum solution of an instance is given and the goal is to determine if one can maintain a good solution when the instance is subject to minor ...
Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem

We consider the integrality gap of the subtour linear program (LP) relaxation of the traveling salesman problem (TSP) restricted to circulant instances. De Klerk and Dobre [Discrete Appl. Math., 159 (2011), pp. 1815--1826] conjectured that the value of ...
New semidefinite programming relaxations for the Linear Ordering and the Traveling Salesman Problem

In 2004 Newman 43 suggested a semidefinite programming relaxation for the Linear Ordering Problem (LOP) that is related to the semidefinite program used in the Goemans-Williamson algorithm to approximate the Max Cut problem (Goemans and Williamson, 1995)...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Discrete Algorithms

Journal of Discrete Algorithms Volume 7, Issue 4

December, 2009

234 pages

ISSN:1570-8667

Issue’s Table of Contents

Copyright © Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 December 2009

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bilò D(2024)New Algorithms for Steiner Tree ReoptimizationAlgorithmica10.1007/s00453-024-01243-286:8(2652-2675)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s00453-024-01243-2
Goyal KMömke T(2020)Robust Reoptimization of Steiner TreesAlgorithmica10.1007/s00453-020-00682-x82:7(1966-1988)Online publication date: 1-Jul-2020
https://dl.acm.org/doi/10.1007/s00453-020-00682-x
Dai WYang Y(2019)Reoptimization of minimum latency problem revisitedJournal of Combinatorial Optimization10.1007/s10878-018-0317-337:2(601-619)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s10878-018-0317-3
Schieber BShachnai HTamir GTamir T(2018)A Theory and Algorithms for Combinatorial ReoptimizationAlgorithmica10.1007/s00453-017-0274-880:2(576-607)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s00453-017-0274-8
Bender MFarach-Colton MFekete SFineman JGilbert S(2017)Cost-Oblivious Storage ReallocationACM Transactions on Algorithms10.1145/307069313:3(1-20)Online publication date: 26-May-2017
https://dl.acm.org/doi/10.1145/3070693
Bender MFarach-Colton MFekete SFineman JGilbert SBlelloch GAgrawal K(2015)Cost-Oblivious Reallocation for Scheduling and PlanningProceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures10.1145/2755573.2755589(143-154)Online publication date: 13-Jun-2015
https://dl.acm.org/doi/10.1145/2755573.2755589
Bender MFarach-Colton MFekete SFineman JGilbert S(2015)Reallocation Problems in SchedulingAlgorithmica10.1007/s00453-014-9930-473:2(389-409)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1007/s00453-014-9930-4
Bender MFarach-Colton MFekete SFineman JGilbert SHull RGrohe M(2014)Cost-oblivious storage reallocationProceedings of the 33rd ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems10.1145/2594538.2594548(278-288)Online publication date: 18-Jun-2014
https://dl.acm.org/doi/10.1145/2594538.2594548
Bender MFarach-Colton MFekete SFineman JGilbert SBlelloch GVöcking B(2013)Reallocation problems in schedulingProceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures10.1145/2486159.2486181(271-279)Online publication date: 23-Jul-2013
https://dl.acm.org/doi/10.1145/2486159.2486181
Archetti CGuastaroba GSperanza M(2013)Reoptimizing the rural postman problemComputers and Operations Research10.1016/j.cor.2012.12.01040:5(1306-1313)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1016/j.cor.2012.12.010

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents