27 problems

Williamson's conjecture. For every $n$, the integrality gap satisfies

For a metric cost vector $\bm{c}$, let an optimal solution of the subtour elimination problem be a vector $\bm{x}\in P_{\operatorname{SEP}}^{n}$ minimizing the relaxed objective. C…

Goemans's conjecture. The integrality gap satisfies

Integrality-gap conjecture. For the $K$-revision hypercube problem,

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

Let $P_{\text{ASEP}}^{n}$ be the asymmetric subtour elimination polytope, let $\boldsymbol{x}$ be one of its vertices, and let $G_{\boldsymbol{x}}$ denote the stabilizer of…

Let $V$) be the node set of a pseudo-quasi-metric asymmetric traveling salesman problem, let $P_{\text{ASEP}}^{n}$ be its asymmetric subtour elimination polytope, and let … Here…

Pure half-integral indegree conjecture. Every such spanning vertex $x$ has indegree $1$ at every Steiner node. Consequently, the PHI procedure is exhaustive for every pure half-int…

Ten-vertex gap conjecture. With $n\leq 10$, the highest integrality gap is

Six-vertex unit-gap conjecture. For $n=6$, the CM and BCR formulations have integrality gap equal to $1$.

PHI indegree conjecture. Every Steiner node of every PHI spanning vertex has indegree exactly one.

Let $m$ be the number of subsets, let $p$ be the inclusion probability, and let $n$ be the number of elements. Write $\operatorname{val}_{\mathrm{GR}}$ for the value produced by th…

Let $m$ be the number of subsets, let $p$ be the inclusion probability, and let $n$ be the number of elements. Write $\operatorname{val}_{\mathrm{GR}}$ for the value produced by th…

Let $m$ be the number of subsets, let $p$ be the inclusion probability, and let $n$ be the number of elements. Write $\operatorname{val}_{\mathrm{GR}}$ for the value produced by th…

The construction recursively extends graphs using randomized graph extensions, with $t$ graphs and appropriately chosen edge lengths. Recursive graph-extension conjecture. Recursiv…

Good-function conjecture. If

Alexander et al.'s conjecture.

De Klerk–Dobre conjecture. For every circulant TSP instance,

Half-integer six-fifths conjecture. If $x\in\mathrm{LP}(G)$ is half-integer, then $\frac{6}{5}x$ dominates a convex combination of 2-edge-connected multigraphs of $G$.

Six-fifths conjecture. If $x\in\mathrm{LP}(G)$, then $\frac{6}{5}x$ dominates a convex combination of 2-edge-connected multigraphs of $G$. Equivalently,

The four-thirds conjecture.

Let $G$ be a connected, undirected graph on vertex set $[n]$, and let the graphic TSP instance assign to each pair $i,j\in[n]$ the cost $c_{ij}$ equal to the length of a shortest…

Let $G=(V,E)$ be a graph, let $T\subseteq V$ be the prescribed set of odd-degree vertices, and let a vector be feasible when it is a convex combination of $T$-tours. Assume that ev…

Let $x$ be a vector in the subtour polytope, and let feasibility mean membership in the convex hull of $T$-tours. The $4/3$-conjecture. The integrality gap of the subtour eliminati…

Scheithauer's conjecture. The integer optimum satisfies