Bounds for the travelling salesman problem under a sharpened triangle inequality

1. Problem

Definition 1. Let \(V\) be a finite set with \(|V|\geq3\). Let \(c:V\times V\to\mathbb{R}_{\geq0}\) be symmetric, with \(c(u,v)>0\) for \(u\ne v\). For a fixed \(\beta\in[1/2,1)\), assume that

for all distinct \(u,v,w\in V\). We seek a minimum-cost Hamiltonian cycle. Write \(\operatorname{OPT}\) for its cost.

The assumption is stronger than the ordinary triangle inequality. It can hold for a finite Euclidean data set when no data point lies on a segment between two other points. It can also arise when every additional leg has a fixed handling, transfer, stop, or setup cost. For a given data set, the smallest admissible parameter is

Thus the model is applicable exactly when \(\widehat\beta<1\). The value of \(\widehat\beta\) should be measured rather than assumed.

2. Upper-bound algorithms

For \(v\in V\), define

Lemma 2 (local edge range). For every \(v\in V\),

Proof. Let \(x\) and \(z\) be a nearest and a farthest neighbour of \(v\), respectively. Apply (1) to the triples \((v,x,z)\) and \((x,v,z)\):

Substitution gives \((1-\beta^2)M_v\leq\beta(1+\beta)m_v\), which is equivalent to (4). \(\square\)

2.1. Shifted Christofides

We first recall the ordinary Christofides proof [2]. A minimum spanning tree costs at most \(\operatorname{OPT}\), because deleting one edge from an optimum tour gives a spanning tree. Let \(D\) be the set of odd-degree vertices of the tree; \(|D|\) is even. Shortcut the optimum tour to a cycle on \(D\). Its two alternating perfect matchings have total cost at most \(\operatorname{OPT}\). Hence a minimum-weight perfect matching on \(D\) costs at most \(\operatorname{OPT}/2\). Adding it to the tree gives an Eulerian graph, and metric shortcutting gives a Hamiltonian cycle of cost at most \(3\operatorname{OPT}/2\).

For each vertex define the maximum safe shift

and set \(d(u,v)=c(u,v)-s_u-s_v\) for \(u\ne v\), with \(d(v,v)=0\). From (5),

which is exactly the triangle inequality \(d(u,w)\leq d(u,v)+d(v,w)\). To prove nonnegativity, fix \(u\ne v\) and choose \(x\notin\{u,v\}\). The inequalities centred at \(u\) and \(v\) are

Their sum gives \(s_u+s_v\leq c(u,v)\), so \(d(u,v)\geq0\). Thus \(d\) is a nonnegative pseudometric.

Every Hamiltonian cycle has degree two at every vertex. Therefore every tour \(H\) satisfies

Inequality (1) also implies

because each term minimized in (5) is at least \((1-\beta)(c(u,v)+c(v,w))\geq2(1-\beta)m_v\).

Lemma 3 (first candidate). Christofides' algorithm applied to \(d\), and then evaluated in \(c\), returns a tour \(H_1\) such that

Proof. By (6), Christofides' bound in \(d\), and (7),

2.2. An oriented opening of a 2-factor

Let \(F\) be a minimum simple undirected 2-factor, that is, a minimum-cost spanning 2-regular subgraph. Each component of \(F\) is a cycle of length at least three, and \(c(F)\leq\operatorname{OPT}\). If \(C\) is a factor cycle and \(a\to b\) is an orientation of one of its edges, define the opening score

Delete \(ab\) and orient the remaining path from \(a\) to \(b\). Thus \(b\) is its exit. The orientation is only a choice of endpoint; the graph and the 2-factor remain undirected.

If \(F\) consists of one cycle, return that cycle. Otherwise, let \(x\) be the start of the next open path and put \(g=c(b,x)\). Then \(g\leq M_b\). Removing \(ab\) and inserting \(bx\) therefore changes the cost by at most

The bound depends on the exit \(b\), but not on the identity of \(x\). Hence each factor cycle can choose its oriented opening independently. The resulting paths may then be put in any cyclic order.

Write \(k=|V(C)|\). Average over the \(2k\) oriented edges of \(C\). Each vertex is the head of two oriented edges, and each undirected edge occurs in two orientations. Hence

Lemma 4 (second candidate). Opening the cycles as above and joining the resulting paths gives a tour \(H_2\) such that

Proof. Sum (10) and (11) over the cycles of \(F\), and then use \(c(F)\leq\operatorname{OPT}\), (4), and (3):

2.3. Balancing the two bounds

Theorem 5. Let \(\operatorname{ALG}_0=\min\{c(H_1),c(H_2)\}\). Then

Proof. Put \(y=S/\operatorname{OPT}\). At each vertex, the two incident optimum-tour edges have total cost at least \(2m_v\); summing gives \(S\leq\operatorname{OPT}\). Conversely, orient the optimum tour and charge each outgoing edge to its tail. By (4), \(\operatorname{OPT}\leq q_\beta S\). Thus

Lemmas 3 and 4 imply

The first affine function decreases with \(y\), and the second increases. They meet at

A direct calculation shows that \(y_0\) lies in the interval (14). Substitution in either term of (15) gives (13). At \(\beta=2/3\), one has \(y_0=5/6\), and both terms equal \(11/9\). \(\square\)

Comparison with the 2000 bound. The published envelope [1] is

For \(1/2<\beta<1\), each term in (17) is strictly larger than \(U(\beta)\). Indeed, the two differences are

respectively. Both are positive. Thus the two-candidate argument alone improves the published envelope throughout the open interval.

2.4. A stronger complement candidate

A newer second candidate gives a shorter proof and a better bound. Put \(B=\sum_{v\in V}M_v\), and define a nonnegative weight on every edge by

The weight is nonnegative because both \(M_u\) and \(M_v\) are at least \(c(u,v)\). Moreover, every Hamiltonian cycle \(T\) satisfies the exact identity

Let \(H_X\) be the tour returned by the published \(4/5\)-approximation for symmetric Max-TSP applied to \(w\). Since maximizing \(w(T)\) is equivalent to minimizing \(c(T)\),

Theorem 6 (complement bound). Returning the cheaper of \(H_1\) and \(H_X\) gives

Proof. Again let \(z=S/\operatorname{OPT}\). By (14), \((1-\beta)/\beta\leq z\leq1\). Equations (8) and (20) give

For \(\beta\leq3/5\), the two lines meet at or beyond \(z=1\), and the maximum of their lower envelope is the second line at \(z=1\). For \(\beta\geq3/5\), they meet inside the interval at

Substitution gives the two branches in (21). In particular, \(z_*=21/22\) and \(U_X(2/3)=13/11\). \(\square\)

The complement candidate also explains the relation with the oriented 2-factor. Before applying (4), the latter has normalized bound \(C_0=2/3+B/(3\operatorname{OPT})\), whereas (20) gives \(X=4/5+B/(5\operatorname{OPT})\). By (19) and the nonnegativity of \(w\), every tour costs at most \(B\), so \(B/\operatorname{OPT}\geq1\), and therefore

The required Max-TSP theorem applies to complete undirected graphs with nonnegative edge weights [3], as in (18). Thus the complement candidate pointwise dominates the oriented 2-factor bound. We retain the 2-factor proof because it is elementary and because its opening argument motivates the witness constructions below.

3. Witness certificates

The proof above records only the aggregate local scale \(S\). A witness certificate also records where the slack in (5) occurs. For each \(v\), choose a pair \(u_v,w_v\) that attains the minimum in (5). The vertex \(v\) sponsors the two edges \(vu_v\) and \(vw_v\). Their undirected union is the support graph \(G\). Each vertex sponsors two distinct edges because one minimizing triangle has exactly two sides incident with \(v\). In particular, \(G\) has minimum degree at least two.

Figure 3. A local witness and a support-path certificate.

Define the nonnegative slack variables

The inequality \(\Delta_v\geq0\) is exactly (7), and \(\Gamma_v\geq0\) is exactly (4). A tour edge need not belong to \(G\). A structural certificate therefore assigns it a short path in \(G\). Repeated use of (1) bounds the direct edge by a weighted sum of the path edges. After the bounds are summed over the tour, the order of summation can be reversed. The tour cost is then controlled by the number of times each sponsored edge occurs in the charging paths.

Three constructions are used. In each connected support component, choose a spanning tree \(T\). Sekanina's theorem [4] gives a Hamiltonian cycle in \(T^3\), so each cycle edge has a tree path of at most three edges. Since \(G\) has minimum degree at least two, Hobbs' theorem [5] gives a 2-factor in \(G^2\), with charging paths of at most two edges. For small support components, a finite atlas stores an explicit cycle and an explicit charging path for every non-support edge. The atlas can have lower sponsor congestion than either general theorem.

Example at \(\beta=2/3\). In Figure 3(b), give every support edge cost \(1\) and every omitted edge cost \(4/3\). Then \(\operatorname{OPT}=16/3\). A three-edge tree path gives

and hence a tour certificate of \(50/9=(25/24)\operatorname{OPT}\). The two-edge support path gives

and certifies the optimum value \(16/3\). This is a local improvement in the certificate; it is not by itself a global approximation theorem.

A global example shows how the extra variables improve a ratio. At \(\beta=2/3\), put \(z=S/\operatorname{OPT}\), \(\delta=\Delta/\operatorname{OPT}\), \(\gamma=\Gamma/\operatorname{OPT}\), and let \(R\) denote the normalized cost of the cheapest available candidate. The two elementary candidates and one order-seven witness candidate satisfy

Exact optimization over the certified feasible region has the following worst intersection:

This is the simplest global witness improvement over Theorem 5. The complement bound in Theorem 6 is stronger at \(\beta=2/3\). The witness planes remain useful in the full portfolio on other parts of the parameter interval.

4. Upper-bound curves

Figure 4 compares the published 2000 envelope, the elementary bound (13), the complement bound (21), and the current computer-derived portfolio. The last curve is represented by eight rational formulas. Exact tests isolate the proposed switch points and check continuity and selected portfolio optima. An interval-wide certificate of phase validity remains to be added.

4.1. Structural graphs

The following plate shows the distinct support graphs, obstructions, tight examples, and reduction gadgets used in the present repository. It does not list every labelled graph in the finite atlases.

The clustered-triangle family in Figure 5(g) is exactly tight for the 2-factor benchmark: if each block is a unit triangle and every inter-block edge has cost \(q_\beta=\beta/(1-\beta)\), then

This structural statement is fully verified in Lean. It is not an inapproximability result for the complete algorithm.

5. A preliminary lower-bound improvement

The repository contains two transfers from bounded-metric TSP hardness [6]. The elementary \(\{1,2\}\)-cost transfer gives

An anisotropic transfer based on the three-role parity ladder in Figure 5(h) gives

The better of (28) and (29) switches at \(\beta_*=0.6130356046\ldots\), the relevant root of \(8\beta^3+23\beta^2-22\beta+3=0\).

At \(\beta=2/3\), the resulting inapproximability threshold is

for every fixed \(\varepsilon>0\), unless \(\mathrm{P}=\mathrm{NP}\). The value obtained from the published 2000 reduction is \(68569/68564\approx1.00007292\). Thus the threshold increases by approximately \(0.00058707\).

The new transfer assigns different shifts to the three vertex roles of the ladder and uses nonlinear values for four source-distance classes. An exact checker reduces the sharpened triangle condition to 154 polynomial inequalities and certifies them by Bernstein coefficients. The source hardness theorem and the complete reduction have not yet been formalized in Lean.

6. Verification status and next steps

The most useful next step is to formalize the graph-algorithm layer of Theorem 5. After that, the finite witness outputs can be imported as small hashed certificates rather than repeated exhaustive searches.