On the length of optimal TSP circuits in sets of bounded diameter (Q762465): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
 
(One intermediate revision by one other user not shown)
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/0095-8956(84)90067-4 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2059988211 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Geometrical Extrema Suggested by a Lemma of Besicovitch / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5573028 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On some applications of graph theory. I / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5344631 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The shortest path and the shortest road through <i>n</i> points / rank
 
Normal rank
Property / cites work
 
Property / cites work: An efficient collision-free protocol for prioritized access-control of cable or radio channels / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Shortest Path Through a Number of Points / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3278735 / rank
 
Normal rank

Latest revision as of 15:51, 14 June 2024

scientific article
Language Label Description Also known as
English
On the length of optimal TSP circuits in sets of bounded diameter
scientific article

    Statements

    On the length of optimal TSP circuits in sets of bounded diameter (English)
    0 references
    1984
    0 references
    For a set V of n points in \({\mathbb{R}}^ k\), let \(\ell (V)\) denote the length of the shortest circuit which passes through all the points of V. Define \(\ell (k,n)=\max \ell (V),\) where the maximum ranges over all sets V having diameter 1. This interesting paper studies \(\ell (k,n)\). The main results are: \[ (\pi^ 2/12)^{1/4}\cdot n^{1/2}\leq \ell (2,n)\leq (\pi /2)^{1/2}\cdot n^{1/2}+O(1)\quad and\quad \] \[ c_ k\cdot n^{1-1/k}\leq \ell (k,n)\leq ((3-\sqrt{3})k/(k-1))\cdot n^{1- 1/k}+o(n^{1-1\quad /k}). \] In the last inequality \(c_ k= \limsup_{n\to \infty}\delta (k,n)n^{1/k}>0,\) where \(\delta\) (k,n) is the maximal possible value over all sets V having diameter 1 of the minimal distance between a pair of points of V.
    0 references
    0 references
    Euclidean traveling salesman problem
    0 references
    shortest circuit
    0 references
    0 references

    Identifiers