Bounds for the traveling salesman paths of two-dimensional modular lattices

• Arlotto A, Steele JM (2013) Beardwood–Halton–Hammersley theorem for stationary ergodic sequences: a counterexample. arXiv:1307.0221v4 [math.PR]

• Beardwood J, Halton J, Hammersley J (1959) The shortest path through many points. Math Proc Camb Philos Soc 55:299–327

  Article  MathSciNet  MATH  Google Scholar 

• Berthé V (2011) Multidimensional Euclidean algorithms, numeration and substitutions. Integers, 11B, Paper A02

• Eisenbrand F (2001) Short vectors of planar lattices via continued fractions. Inform Process Lett 79:121–126

  Article  MathSciNet  MATH  Google Scholar 

• Gao J, Steele JM (1994) General spacefilling curve heuristics and limit theory for the traveling salesman problem. J Complex 10:230–245

  Article  MathSciNet  MATH  Google Scholar 

• Karloff H (1989) How long can a Euclidean traveling salesman tour be? SIAM J Discret Math 2(1):91–99

  Article  MathSciNet  MATH  Google Scholar 

• Kuipers L, Niederreiter H (1974) Uniform distribution of sequences. Wiley, New York

  MATH  Google Scholar 

• Meester R (1999) A simple proof of the exponential convergence of the modified Jacobi–Perron algorithm. Ergodic Theory Dyn Sys 19:1077–1083

  Article  MathSciNet  MATH  Google Scholar 

• Niederreiter H (1992) Random number generation and Quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol 63. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA

• Pausinger F, Steinerberger S (2016) On the discrepancy of jittered sampling. J Complex 33:199–216

  Article  MathSciNet  MATH  Google Scholar 

• Pausinger F, Topuzoğlu A (2014) Permutations of finite fields and uniform distribution modulo 1, algebraic curves and finite fields. In: Niederreiter H, Ostafe A, Panario D, Winterhof A (eds) Radon series on applied and computational mathematics, vol 16, pp 145–160

• Perron O (1907) Grundlagen für eine Theorie des Jacobischen Kettenbruchalgorithmus. Math Ann 64:1–76

  Article  MathSciNet  MATH  Google Scholar 

• Perron O (1921) Über diophantische approximationen. Math Ann 83:77–84

  Article  MathSciNet  MATH  Google Scholar 

• Platzman LK, Bartholdi J (1989) Spacefilling curves and the planar traveling salesman problem. J Assoc Comput Mach 36:719–737

  Article  MathSciNet  MATH  Google Scholar 

• Raju N (1976) Periodic Jacobi–Perron algorithms and fundamental units. Pac J Math 64:241–251

  Article  MathSciNet  MATH  Google Scholar 

• Rote G (1997) Finding a shortest vector in a two-dimensional lattice modulo \(m\). Theor Comput Sci 172:303–308

  Article  MathSciNet  MATH  Google Scholar 

• Schratzberger B (1998) The exponent of convergence of Brun’s algorithm in two dimensions. Sitzungsber Abt II(207):229–238

  MathSciNet  MATH  Google Scholar 

• Schweiger F (1996) The exponent of convergence for the 2-dimensional Jacobi–Perron algorithm. In: Nowak WG, Schoissengeier J (eds) Proceedings of the conference on analytic and elementary number theory, Vienna, pp 207–213

• Schweiger F (2000) Multidimensional continued fractions. Oxford University Press, Oxford

  MATH  Google Scholar 

• Steele JM (1980) Shortest path through pseudorandom points in the \(d\)-cube. Proc Am Math Soc 80:130–134

  MathSciNet  MATH  Google Scholar 

• Steinerberger S (2010) A new lower bound for the geometric traveling salesman problem in terms of discrepancy. Oper Res Lett 38:318–319

  Article  MathSciNet  MATH  Google Scholar 

• Steinerberger S (2015) New bounds for the traveling salesman constant. Adv Appl Probab 47:27–36

  Article  MathSciNet  MATH  Google Scholar 

Download references