95 problems

Cohn–Elkies lifting conjecture. Every optimal solution $f$ can be lifted to such a function $h$ with the same value of $r$ and

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…

Consider the modified version of Algorithm $\mathrm{AhdLAMulti}$ in which the dual price for the first batch is computed using only information from customers arriving in that batc…

Four-thirds integrality-gap conjecture. The subtour elimination linear program for the metric TSP has integrality gap exactly $\frac{4}{3}$.

Goemans's conjecture. The integrality gap satisfies

Let $P$ be a $d$-dimensional polytope with $n$ facets, and let ${\bf c}$ be a generic linear functional. Orient the graph of $P$ according to increasing values of ${\bf c}$, and de…

Dedieu–Shub conjecture. The total curvature of the central path is linearly bounded in the dimension of the ambient space.

Continuous $d$-step Conjecture. The function $\Lambda(2d,d)$ grows linearly in its input; that is,

A sharp configuration is a configuration for which the linear programming bound for spherical codes is attained. The techniques conjecture. The techniques developed in the paper ap…

For a linear program with dimension $n$, consider a descent path, meaning a sequence of pivots that decreases the objective function at each step. Linear descent-path conjecture. T…

Linear-programming improvement conjecture. Linear programming methods could be used to improve the constants in Theorem.

Let $\Lambda$ be a lattice in $\mathbb{R}^{24}$ and let $g$ be the Schwartz function constructed by the paper's linear-programming method, with $g(x)\leq 0$ beyond the relevant vec…

Assume that all nonzero vectors of a lattice $\Lambda\subset\mathbb{R}^{24}$ have length exactly $2$ or at least $\sqrt{6}$. Let $g\colon\mathbb{R}^{24}\to\mathbb{R}$ be a Schwartz…

Linear-growth conjecture. The worst-case total curvature of a central path is $O(n)$.

A linear programming instance is specified by rational data, and an algorithm is strongly polynomial if its number of arithmetic operations and the sizes of the intermediate number…

Consider the random K-LSAT linear program with $n$ variables and $m$ constraints, with all auxiliary variables $\psi$ set to zero. Let $N(n,m)$ be the maximum cardinality of a feas…

Let $c^*_K$ be the constant introduced in the source's theorem for the optimal value ${\cal LP}(n,c)$ of the random K-LSAT linear program, and consider the corresponding feasibilit…

Consider LP decoding of a low-density-parity-check code, and let selected bits lie on a critical loop identified through the loop-calculus expansion. For each such bit, the decoder…

Consider linear-programming (LP) decoding as a large-signal-to-noise-ratio limit of belief-propagation decoding, and suppose that an LP modification is required to preserve the lin…

Planar LP sharpness conjecture. The linear program is sharp at value

Cohn–Rajagopal's conjecture. Every such valid four-colored configuration has center density at most $1$.

Let $\alpha$ be the middle real root of … For odd $n=2m+1$, let $L_m^{\mathrm{fat}}$ and $L_m^{\mathrm{thin}}$ denote the relaxation optima on the fat and thin colour classes, resp…

Let $P=\\{x\in \mathbb{R}^n: A x=b, x\geq 0\\}$, where $A\in \mathbb{R}^{m\times n}$ has full row rank. An elementary vector is a support-minimal nonzero vector in $\ker(A)$, and a…

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