25 problems

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…

Bollobás–Meir conjecture. For any finite set of points $X\subseteq[0,1]^k$, there exists a Hamiltonian cycle $H$ on $X$ with $S_k(H)\leq 2\cdot k^{k/2}$ if $k\neq3$, and…

Goemans's conjecture. The integrality gap satisfies

Let the input to the Traveling Salesman Problem consist of the locations of finitely many cities, and let the desired output be a shortest route through them. The input is represen…

Consider the traveling salesman problem for cities in a two-dimensional domain, with constrained tours and subtracted mean length described by the scaling quantities above. The par…

Asymptotic constant conjecture.

Let $P_{\text{ASEP}}^{n}$ be the asymmetric subtour elimination polytope, let $\boldsymbol{x}$ be a vertex of this polytope, and let $\mathcal{N}(\boldsymbol{x})$ denote its neighb…

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…

Bertsimas–Grigni conjecture. For every linear order $\leq$ on the unit square,

Hamiltonian-path conjecture. The equalities

Connected bipartite $\kappa$-factor conjecture. The connected bipartite $\kappa$-factor problem should allow for a similar analysis to that developed for the concave one-dimensiona…

Let $g_1$, $g_1+2m$, and the upper and lower bounds denote the parameters and tour costs defined for the two-stripe symmetric circulant traveling salesman problem. In particular, l…

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…

Schalekamp–Sebő–Traub conjecture. The integrality gap of $({\mathsf{Subtour\mhyphen LP}})$ is achieved on instances having an optimal fractional solution that is half integral.

Four-thirds conjecture. The integrality gap of $({\mathsf{Subtour\mhyphen LP}})$ is $\frac43$.

For a metric Traveling Salesman instance, define the integrality ratio as the ratio of the length of an optimum tour to the length of an optimum solution to the subtour linear prog…

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…

For a graph $G$, consider the subtour elimination linear program for the metric traveling salesman problem, whose integrality gap is the supremum, over instances, of the ratio betw…

Three-dimensional TSPN hardness conjectures. Approximating TSPN for connected regions in $\mathbb{R}^3$ within a factor $O(\log^{1/2} n)$ and TSPN for disconnected regions in…

Let a tour be a traveling-salesman tour, and let the subtour relaxation be the standard linear-programming relaxation whose optimum value is a lower bound on the length of an optim…

Consider extreme points of the Held–Karp relaxation on $n$ vertices, and let the maximum degree of an extreme point mean the maximum degree of its support graph. The maximum-degree…

For the Held–Karp relaxation of the Traveling Salesman Problem, let $\operatorname{OPT}_{\mathrm{HK}}$ be its optimum value and let $\operatorname{OPT}_{\mathrm{TSP}}$ be the optim…

Let $P_n$ be the Graphical Traveling Salesman Polyhedron, let $mathcal G_B$ be the graph associated with a relaxation $mathcal R_B$, and call a facet of $P_n$ an NR-facet when it h…