3 problems

Consider the metric traveling salesperson problem and its subtour linear programming relaxation. A feasible solution is half-integral if every edge variable satisfies…

Grötschel–Padberg conjecture. For every integer $n\geq 5$, the diameter of the skeleton of the symmetric traveling salesperson polytope is

Let $G_{{\mathcal X},p}$ be the randomly embedded random graph on $n$ points in $[0,1]^d$, with edge-probability $p$, and let $T(G_{{\mathcal X},p})$ denote the length of a minimum…