Abstract
It is the first time that bounded degree graph is proven to be computed for a big class of TSP in polynomial time based on frequency quadrilaterals. As TSP conforms to the properties of frequency quadrilaterals, a polynomial algorithm is given to reduce complete graph of TSP to bounded degree graph in which the optimal Hamiltonian cycle is preserved with a probability above 0.5. For TSP on such bounded degree graphs, there are more competitive exact and approximation algorithms.
Supported by State Key Lab of Alternate Electrical Power System with Renewable Energy Sources, China.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Cook, W.J.: In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press, Princeton (2011)
Gutin, G., Punnen, A.-P.: The Traveling Salesman Problem and Its Variations. Combinatorial Optimization, Springer, London (2007)
de Berg, M., Bodlaender, H.-L., Kisfaludi-Bak, S., Kolay, S.: An ETH-tight exact algorithm for Euclidean TSP. In: The 59th Symposium on Foundations of Computer Science, FOCS 2018, pp. 450–461. IEEE, New York (2018)
Karlin, A.-R., Klein, N., Gharan, S.-O.: A (slightly) improved approximation algorithm for metric TSP. In: The 53rd Symposium on Theory of Computing, STOC 2021, pp. 32–45. ACM, New York (2021)
Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: The traveling salesman problem in bounded degree graphs. ACM Trans. Algorithms 8(2), 1–18 (2012)
Jonker, R., Volgenant, T.: Nonoptimal edges for the symmetric traveling salesman problem. Oper. Res. 32(4), 837–846 (1984)
Hougardy, S., Schroeder, R.T.: Edge elimination in TSP instances. In: Kratsch, D., Todinca, I. (eds.) WG 2014. LNCS, vol. 8747, pp. 275–286. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-12340-0_23
Wang, Y., Remmel, J.-B.: A binomial distribution model for travelling salesman problem based on frequency quadrilaterals. J. Graph Algorithms Appl. 20(2), 411–434 (2016)
Karp, R.: On the computational complexity of combinatorial problems. Networks (USA) 5(1), 45–68 (1975)
Held, M., Karp, R.: A dynamic programming approach to sequencing problems. J. Sco. Ind. Appl. Math. 10(1), 196–210 (1962)
Bellman, R.: Dynamic programming treatment of the travelling salesman problem. J. ACM 9(1), 61–63 (1962)
Björklund, A.: Determinant sums for undirected Hamiltonicity. In: The 51st Symposium on Foundations of Computer Science, FOCS 2010, pp. 173–182. IEEE, New York (2010)
Yuan, Y., Cattaruzza, D., Ogier, M., Semet, F.: A branch-and-cut algorithm for the generalized traveling salesman problem with time windows. Eur. J. Oper. Res. 286(3), 849–866 (2020)
Applegate, D.-L., et al.: Certification of an optimal TSP tour through 85900 cities. Oper. Res. Lett. 37(1), 11–15 (2009)
Cook, W.: The traveling salesman problem: postcards from the edge of impossibility (Plenary talk). In: The 30th European Conference on Operational Research, Dublin, Ireland (2019)
Kisfaludi-Bak, S., Nederlof, J., Wegrzycki, K.: A gap-ETH-tight approximation scheme for Euclidean TSP arXiv:2011.03778v2 (2021)
Eppstein, D.: The traveling salesman problem for cubic graphs. J. Graph Algorithms Appl. 11(1), 61–81 (2007)
Liśkiewicz, M., Schuster, M.R.: A new upper bound for the traveling salesman problem in cubic graphs. J. Discret. Algorithms 27, 1–20 (2014)
Xiao, M.-Y., Nagamochi, H.: An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure. Algorithmica 74(2), 713–741 (2016). https://doi.org/10.1007/s00453-015-9970-4
Dorn, F., Penninkx, E., Bodlaender, H.-L., Fomin, F.-V.: Efficient exact algorithms on planar graphs: exploiting sphere cut decompositions. Algorithmica 58(3), 790–810 (2010). https://doi.org/10.1007/s00453-009-9296-1
Boyd, S., Sitters, R., van der Ster, S., Stougie, L.: The traveling salesman problem on cubic and subcubic graphs. Math. Program. 144(1���2), 227–245 (2014). https://doi.org/10.1007/s10107-012-0620-1
Correa, J.-R., Larré, O., Soto, J.-A.: TSP tours in cubic graphs: beyond 4/3. SIAM J. Discret. Math. 29(2), 915–939 (2015)
Klein, P.: A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights. SIAM J. Comput. 37(6), 1926–1952 (2008)
Borradaile, G., Demaine, E.-D., Tazari, S.: Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs. Algorithmica 68(2), 287–311 (2014). https://doi.org/10.1007/s00453-012-9662-2
Svensson, O., Tarnawski, J., Végh, L.-A.: A constant-factor approximation algorithm for the asymmetric traveling salesman problem arXiv:1708.04215pdf (2019)
Traub, V., Vygen, J.: An improved approximation algorithm for ATSP. In: The 52nd Symposium on Theory of Computing, STOC 2020, pp. 1–13. ACM, New York (2020)
Erickson, J., Sidiropoulos, A.: A near-optimal approximation algorithm for asymmetric TSP on embedded graphs arXiv:1304.1810v2 (2013)
Kawarabayashi, K., Sidiropoulos, A.: Polylogarithmic approximation for Euler genus on bounded degree graphs. In: The 51st Symposium on the Theory of Computing, STOC 2019, pp. 164–175. ACM, New York (2019)
Taillard, E.-D., Helsgaun, K.: POPMUSIC for the traveling salesman problem. Eur. J. Oper. Res. 272(2), 420–429 (2019)
Turkensteen, M., Ghosh, D., Goldengorin, B., Sierksma, G.: Tolerance-based branch and bound algorithms for the ATSP. Eur. J. Oper. Res. 189(3), 775–788 (2008)
Wang, Y., Remmel, J.: A method to compute the sparse graphs for traveling salesman problem based on frequency quadrilaterals. In: Chen, J., Lu, P. (eds.) FAW 2018. LNCS, vol. 10823, pp. 286–299. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78455-7_22
Wang, Y.: Bounded degree graphs computed for traveling salesman problem based on frequency quadrilaterals. In: Li, Y., Cardei, M., Huang, Y. (eds.) COCOA 2019. LNCS, vol. 11949, pp. 529–540. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-36412-0_43
Wang, Y.: Sufficient and necessary conditions for an edge in the optimal Hamiltonian cycle based on frequency qudrilaterals. J. Optim. Theory Appl. 181(2), 671–683 (2019). https://doi.org/10.1007/s10957-018-01465-9
Wang, Y., Han, Z.: The frequency of the optimal Hamiltonian cycle computed with frequency quadrilaterals for traveling salesman problem. In: Zhang, Z., Li, W., Du, D.-Z. (eds.) AAIM 2020. LNCS, vol. 12290, pp. 513–524. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-57602-8_46
Wang, Y.: Special frequency quadrilaterals and an application. In: Sun, X., He, K., Chen, X. (eds.) NCTCS 2019. CCIS, vol. 1069, pp. 16–26. Springer, Singapore (2019). https://doi.org/10.1007/978-981-15-0105-0_2
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Wang, Y. (2022). The Polynomial Randomized Algorithm to Compute Bounded Degree Graph for TSP Based on Frequency Quadrilaterals. In: Cai, Z., Chen, Y., Zhang, J. (eds) Theoretical Computer Science. NCTCS 2022. Communications in Computer and Information Science, vol 1693. Springer, Singapore. https://doi.org/10.1007/978-981-19-8152-4_5
Download citation
DOI: https://doi.org/10.1007/978-981-19-8152-4_5
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-19-8151-7
Online ISBN: 978-981-19-8152-4
eBook Packages: Computer ScienceComputer Science (R0)