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

Florian Pausinger

doi:10.1007/s10878-016-0043-7

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

Florian Pausinger^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	1378-1394
Number of pages	17
Journal	Journal of Combinatorial Optimization
Volume	33
Issue number	4
Early online date	21 Jun 2017
DOIs	https://doi.org/10.1007/s10878-016-0043-7
Publication status	Published - 2018
Externally published	Yes

Keywords

Jacobi–Perron algorithm
Kronecker point set
Modular lattice
Traveling salesman path

ASJC Scopus subject areas

Computer Science Applications
Discrete Mathematics and Combinatorics
Control and Optimization
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1007/s10878-016-0043-7

Cite this

@article{f75c2bb51f19455992341e5e23cc9847,

title = "Bounds for the traveling salesman paths of two-dimensional modular lattices",

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.",

keywords = "Jacobi–Perron algorithm, Kronecker point set, Modular lattice, Traveling salesman path",

author = "Florian Pausinger",

year = "2018",

doi = "10.1007/s10878-016-0043-7",

language = "English",

volume = "33",

pages = "1378--1394",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "4",

}

TY - JOUR

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

AU - Pausinger, Florian

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - Jacobi–Perron algorithm

KW - Kronecker point set

KW - Modular lattice

KW - Traveling salesman path

UR - http://www.scopus.com/inward/record.url?scp=85028247034&partnerID=8YFLogxK

U2 - 10.1007/s10878-016-0043-7

DO - 10.1007/s10878-016-0043-7

M3 - Article

AN - SCOPUS:85028247034

SN - 1382-6905

VL - 33

SP - 1378

EP - 1394

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 4

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this