On a Traveling Salesman Problem for Points in the Unit Cube

József Balogh, Felix Christian Clemen, Adrian Dumitrescu

Research output: Contribution to journalArticlepeer-review

Abstract

Let X be an n-element point set in the k-dimensional unit cube [0,1]k where k≥2. According to an old result of Bollobás and Meir (Oper Res Lett 11:19–21, 1992), there exists a cycle (tour) x1,x2,…,xn through the n points, such that ∑i=1n|xi-xi+1|k1/k≤ck, where |x-y| is the Euclidean distance between x and y, and ck is an absolute constant that depends only on k, where xn+1≡x1. From the other direction, for every k≥2 and n≥2, there exist n points in [0,1]k, such that their shortest tour satisfies ∑i=1n|xi-xi+1|k1/k=21/k·k. For the plane, the best constant is c2=2 and this is the only exact value known. Bollobás and Meir showed that one can take ck=9231/k·k for every k≥3 and conjectured that the best constant is ck=21/k·k, for every k≥2. Here we significantly improve the upper bound and show that one can take ck=35231/k·k or ck=2.91k(1+ok(1)). Our bounds are constructive. We also show that c3≥27/6, which disproves the conjecture for k=3. Connections to matching problems, power assignment problems, related problems, including algorithms, are discussed in this context. A slightly revised version of the Bollobás–Meir conjecture is proposed.

Original languageEnglish (US)
Pages (from-to)3054-3078
Number of pages25
JournalAlgorithmica
Volume86
Issue number9
DOIs
StatePublished - Sep 2024

Keywords

  • Binary code
  • Minimum spanning tree
  • Relaxed triangle inequality
  • Traveling salesman problem

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'On a Traveling Salesman Problem for Points in the Unit Cube'. Together they form a unique fingerprint.

Cite this