Lower bounds for the universal TSP on the plane
Cosmas Kravaris · 2024
Read Lower bounds for the universal TSP on the plane by Cosmas Kravaris (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-16448.txt.
Introduction
Cosmas Kravaris sharpens, in a solo 2024 mathematics paper, a lower bound for a one-size-fits-all tour rule. The traveling salesman task asks for the shortest path through a set of points. A universal rule fixes one master order of the unit square in advance, then visits any point set in that order. Past work showed some sets force such tours to run long.
Kravaris raises that floor. For any master order, he builds point sets of any size whose forced tour runs long by a set factor over the best tour. The factor improves the previous bound from a known 2006 result. His proof splits long walks on a cycle into two kinds. A walk either zigzags between two far points, or it stays inside a set of small diameter for a long time. That split drives the bound.
Catalog record
| CREATOR | Cosmas Kravaris |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-16448
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Lower bounds for the universal TSP on the plane Cosmas Kravaris Abstract . We show a lower bound for the universal traveling salesman heuristic on the plane: for any linear order on the unit square [ 0 , 1 ] 2 [0,1]^{2} , there are finite subsets S ⊂ [ 0 , 1 ] 2 S\subset[0,1]^{2} of arbitrarily large size such that the path visiting each element of S S according to the linear order has length ≥ C log | S | / log log | S | \geq C\sqrt{\log|S|/\log\log|S|} times the length of the shortest path visiting each element in S S . ( C > 0 C>0 is a constant that depends only on the linear order.) This improves the previous lower bound ≥ C log | S | / log log | S | 6 \geq C\sqrt[6]{\log|S|/\log\log|S|} of [ HKL06 ] . The proof establishes a dichotomy about any long walk on a cycle: the walk either zig-zags between two far away points, or else for a large amount of time it stays inside a set of small diameter. 1. Introduction Let (\mathcal{M},d) be a metric space. For any linear order \leq on \mathcal{M} and any finite subset \{s_{1},...s_{n}\}\subset\mathcal{M} , indexed such that s_{1}<s_{2}<...<s_{n} , the cost of visiting each point in the set according to \leq is cost_{\leq}(\{s_{1},...s_{n}\}):=\sum_{i=1}^{n-1}d(s_{i},s_{i+1}). The traveling salesman problem (TSP) asks for the smallest cost among all possible ways we can order the points S=\{s_{1},...,s_{n}\} . We write tsp(\{s_{1},...,s_{n}\}):=\inf_{\pi\in Sym_{n}}\sum_{i=1}^{n-1}d(s_{\pi(i)},s_{\pi(i+1)}), where Sym_{n} denotes the set of all permutations on \{1,...,n\} . The TSP competitive ratio function or order ratio function of a linear order \leq on \mathcal{M} is OR_{\leq}(n):=\sup_{S\subset\mathcal{M}:\;|S|\leq n}\dfrac{cost_{\leq}(S)}{tsp(S)},\;\;\;where\;n\in\mathbb{N}. In [ PBI89 ] , Bartholdi and Platzman introduced the universal traveling salesman problem , a heuristic for the traveling salesman problem. Using the Sierpinski space-filling curve f:[0,1]\to[0,1]^{2} they defined a linear order \leq_{BP} on [0,1]^{2} by s\leq_{BP}s^{\prime}\iff\min\{t\in[0,1]|f(t)=s\}\leq\min\{t\in[0,1]|f(t)=s^{\prime}\}. They proved that for every n\in\mathbb{N} OR_{\leq_{BP}}(n)\lesssim\log n and conjectured that OR_{\leq_{BP}}(n)\lesssim 1 . (Recall that for two sequences \{a_{n}\}_{n},\{b_{n}\}_{n}\subset\real^{+} one has a_{n}\lesssim b_{n} if and only if b_{n}\gtrsim a_{n} if and only if there exists 0<C<\infty such that a_{n}\leq Cb_{n} for all n\in\mathbb{N} . Also, we write a_{n}\asymp b_{n} when a_{n}\lesssim b_{n} and b_{n}\lesssim a_{n} .) Their conjecture was disproved by Bertsimas and Grigni [ BG89 ] who showed that OR_{\leq_{BP}}(n)\gtrsim\log n, and conjectured that this lower bound holds for all linear orders on [0,1]^{2} . {conj} [Bertsimas, Grigni] For any linear order \leq on the unit square ([0,1]^{2},||\cdot||_{2}) OR_{\leq}(n)\gtrsim\log n. In [ HKL06 ] , Hajiaghayi, Kleinberg and Leighton showed that any linear order \leq on [0,1]^{2} has OR_{\leq}(n)\gtrsim\sqrt[6]{\dfrac{\log n}{\log\log n}}. In [ EM20 ] , Eades and Mestre proved the conjecture for a special family of orders called ”hierarchical”. The purpose of this paper is to prove the following theorem: {theo} For any linear order \leq on the unit square ([0,1]^{2},||\cdot||_{2}) OR_{\leq}(n)\gtrsim\sqrt{\dfrac{\log n}{\log\log n}}, that is, for any n\in\mathbb{N} there exists an n -point set S\subset[0,1]^{2} with cost_{\leq}(S)\geq C\sqrt{\dfrac{\log n}{\log\log n}}\;tsp(S), where C>0 is a constant independent of n and S . Similar to [ HKL06 ] , there are two types of obstructions to a small competitive ratio function, backtracks and zig-zags, and we show that at least one of the two must occur. Each obstruction corresponds to a set S with cost_{\leq}(S)\geq C\sqrt{\log|S|/\log\log|S|}\;tsp(S). The first type is a backtracking set : all points are close to a line L and the ordering of S backtracks a lot for many relevant distance scales (the idea goes back to [ BG89 ] ). Each dyadic square in [0,1]^{2} contains an individual backtrack in some direction, and the set S is the union of backtracks which are close to L and have the same direction as L . The key idea is the definition of a ”backtrack” which allows us to improve the lower bound. We follow the method of [ HKL06 ] which dealt with a different notion of backtrack, insufficient for our purposes. The second type of obstruction is a zig-zag : all points in S lie close to one of three line segments, and the linear order on S jumps back and forth many times between the three segments. The construction of the zig-zag set here is new. It relies on a dichotomy about walks of length M^{2} on the M -cycle. For any 1\leq s\leq M^{1/3} , either there are two points of distance s^{2} apart such that the walk zig-zags between them M/2s many times, or else for s^{3} consecutive steps, the walk is confined within a set of diameter 6s^{2}+2 . We remark that the universal traveling salesman problem can be studied on any metric space, not just the Euclidean plane. The reader may look at [ JLN+05 , GHR06 , GKSS10 , BCK11 , CS17 , EM23b , EM23a , Mit22 ] and references within for variations of the universal traveling salesman problem on other spaces in metric geometry. 2. The setting We begin the proof of Theorem 1. We use the order gap property for doubling metric spaces due to Erschler and Mitrophanov [ EM23a ] : for any linear order \leq on [0,1]^{2} either OR_{\leq}(n)\lesssim\log n or else OR_{\leq}(n)=n for all n\in\mathbb{N} . (Without this property we get the theorem for infinitely many values of n .) Clearly, it suffices to prove the lower bound for powers of 2 . Suppose the contrary: there exists a linear order \leq on [0,1]^{2} , a sequence r_{k}\to\infty and a sequence \epsilon_{k}\to 0 such that OR(2^{r_{k}+2})\leq\epsilon_{k}\sqrt{\dfrac{r_{k}}{\log r_{k}}}. Fix two parameters: r\in\mathbb{N} , the number of scales , and M\in\mathbb{N} , the number of angles . Assume that 180^{2}<M\leq 10^{-5}(r/\log r)^{1/9} . We will show that CASE A : either there exists a subset of size \leq 2^{r+2} with competitive ratio \geq 10^{-4}\sqrt{\dfrac{r}{M^{9}\log r}} , CASE B : or there exists a subset of size \lesssim M^{2/3} with competitive ratio \gtrsim M^{1/3} . Once we show this dichotomy, we are done: choose any sequence M_{k}<\min\{10^{-5}(r/\log r)^{1/9},(10^{4}\epsilon_{r_{k}})^{-2/9}\} such that M_{k}\to\infty as k\to\infty . If CASE B holds for infinitely many k , then this contradicts the first scenario in the dichotomy of Erschler and Mitrophanov, meaning that OR(n)=n for all n\in\mathbb{N} . Else CASE B holds only for finitely many k , in which case there exists k and a subset of size \leq 2^{r_{k}+1} with competitive ratio \geq 10^{-4}\sqrt{r_{k}/M^{9}\log r_{k}}>\epsilon_{k}\sqrt{r_{k}/\log r_{k}} and we arrive at a contradiction. {defi} A backtrack (p,L,\sigma,R_{1},R_{2}) of length l>0 and width w>0 consists of: a line L of slope \{\dfrac{2\pi}{M},2\dfrac{2\pi}{M},3\dfrac{2\pi}{M},...,2\pi\} , a point p\in[0,1]^{2} of distance <w from L , a strip \sigma which is the w -neighborhood of line L , and two rectangular regions R_{1},R_{2}\subset[0,1]^{2} of width w and length l which lie in \sigma in opposite sides of p satisfying: p<q\;\;\;for\;all\;q\in R_{1}\cup R_{2}. Fix two parameters, the length 0<l<1 and the width 0<w<l which depend on r and M (at the end of the proof we will optimize and take l\asymp M^{-4} and w\asymp\sqrt{M\log r/r} ). For each scale t=0,...,r consider all dyadic subsquares of [0,1]^{2} of scale t . There are 2^{2t} many squares Q in total and they partition