6 problems

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

The 4/3 integrality-gap conjecture. The worst-case ratio between the IP and LP optimal values for the metric TSP is exactly

Let $x$ be a half-integral fractional solution of the subtour linear programming relaxation for a metric traveling salesperson problem instance. Sample a random spanning tree from…

Let $G$ be a graph with distinct terminals $s$ and $t$. The integrality ratio is the ratio between the minimum length of an $s$-$t$-tour and the optimum value of the subtour-elimin…

Let $\beta_\mathrm{TSP}^d$ denote the asymptotic constant for the length of a minimum Traveling Salesperson Tour through random points in $[0,1]^d$, so that … Bertsimas and Van Ryz…

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…