2 problems

Let an instance have a fixed number of vertices, and let $x^*$ be an optimal fractional solution of its subtour LP. The two-disjoint-triangles conjecture. The instances maximizing…

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…