nach oben

Journal of Combinatorial Optimization

Erschienen in:

21.06.2016

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

verfasst von: Florian Pausinger

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We present tight upper and lower bounds for the traveling salesman path through the points of two-dimensional modular lattices. We use these results to bound the traveling salesman path of two-dimensional Kronecker point sets. Our results rely on earlier work on shortest vectors in lattices as well as on the strong convergence of Jacobi–Perron type algorithms.

Vorheriger Artikel A new graph parameter and a construction of larger graph without increasing radio k-chromatic number

Nächster Artikel A new effective branch-and-bound algorithm to the high order MIMO detection problem

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

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–327MathSciNetCrossRefMATH

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–126MathSciNetCrossRefMATH

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

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

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

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

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–216MathSciNetCrossRefMATH

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–76MathSciNetCrossRefMATH

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

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

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

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

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

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, OxfordMATH

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

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

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

Titel: Bounds for the traveling salesman paths of two-dimensional modular lattices
verfasst von: Florian Pausinger
Publikationsdatum: 21.06.2016
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 4/2017
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-016-0043-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2017

Even factors of graphs

On the coefficients of the independence polynomial of graphs

On irreducible no-hole L(2, 1)-coloring of subdivision of graphs

A tighter insertion-based approximation of the crossing number

The solution of a generalized secretary problem via analytic expressions

Optimal RSUs placement with delay bounded message dissemination in vehicular networks