= Weighted mismatch bound for Euclidean tours
{title2=$\operatorname{TS}(x)-\operatorname{TS}(y)\leq\sum_{i:x_i\ne y_i}a_i(x)$}
For every configuration $x$ in the unit square there are nonnegative weights $a_i(x)$ such that $\sum_i a_i(x)^2\leq16$ and
$$
\operatorname{TS}(x)-\operatorname{TS}(y)\leq\sum_{i:x_i\ne y_i}a_i(x)\quad\text{for every }y.
$$
Use the sums of the two incident edge lengths in a tour from the <squared edge bound for tours in the unit square>. Runs of missing vertices can be added by the cheaper of two out-and-back detours. This connects <Euclidean travelling salesman tours> to <Talagrand's convex distance inequality>.
Back to article page
