123 problems

Thin tree conjecture. Every $k$-edge-connected graph contains a spanning tree whose thinness is $o(k)$.

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

Approximation conjecture. There is a function $f$ such that for every integer $k$, there is a polynomial-time algorithm which, given a tournament $T$, correctly concludes that…

Let $\phi$ be a doubly stochastic $n\times n$ matrix, so that its entries are non-negative and every row and column sums to $1$. The permanent is denoted by…

Let $R=(r_1,\ldots,r_m)$ and $C=(c_1,\ldots,c_n)$ be positive integer vectors satisfying … A contingency table with margins $(R,C)$ is an $m\times n$ non-negative integer matrix wi…

Let $N=nt$, where $n$ is the dimension and $t$ is the common line sum of an $n\times n$ magic square. The paper gives an approximation algorithm for $|\Sigma(n,t)|$ with running ti…

Potts critical-temperature conjecture. For the Potts model, the critical inverse temperature behaves as

MRF partition-function conjecture. Polynomial-time algorithms for computing the partition function of an MRF can be constructed under a weaker assumption than $$ .

Low-alpha correlation-decay conjecture. Correlation decay on the computation tree holds for much lower values of $\alpha$.

Potts correlation-decay conjecture. Correlation decay can in fact be established in the regime

The optimality conjecture. The particular polynomial $S_{n,n-m}$ is optimal in the sense that

Consider the multi-commodity extension of the Stackelberg network pricing problem, in which each commodity has an associated demand and the relaxation is obtained by summing the si…

Greedy common-superstring conjecture. Greedy produces a common superstring $t'$ of length at most $2s$.

Bounded-size inversion approximation hardness conjecture. There exists $\varepsilon>0$ such that, unless $P=NP$, for every $p\geq 3$ and every $k\geq 1$, no polynomial-time…

Consider the flow-shop scheduling problem $P \mid a_i \in \{0,1\},\ p_j \in \mathbb{Z} \mid \sum w_j C_j(\alpha)$, where $a_i$ are job arrival times, $p_j$ are processing times,…

Morell–Skutella-type conjecture. Given a $b$-transshipment $x$, one can efficiently compute an unsplittable $b$-transshipment $y$ such that

Let $n$ be the number of cars in a Binary Paint Shop Problem instance, and let $\Delta_C$ denote the number of paint swaps produced by a colouring algorithm. Write…

Let $G$ be a graph, let $V_G$ denote its vertex set, and let $|\chi\rangle$ be a magic graph state whose parameters are varied over the collection $\{\theta_{ij}\}$. Let…

Let $G$ be a generalized split graph, a chordal graph, or a co-chordal graph, and consider Algorithm with the look-ahead requirement removed. Look-ahead-free rounding conjecture. T…

Local algorithms, also known as factors of IID, produce solutions to random sparse instances of problems such as MaxCut and MaxSAT. Low-degree polynomials are a class of algorithms…

Optimality conjecture. When $c=\gamma=1$, the coefficient $\gamma^2/(1+c\gamma^2)$ is optimal; equivalently, no higher approximation coefficient is possible for the corresponding o…

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

Abelian embedding conjecture. For a distribution $\mu$ on $\Sigma^k$, Conclusion $$ holds if and only if $\mu$ admits no Abelian embedding.

LLL approximation-barrier conjecture. The state-of-the-art LLL algorithm for $\mathrm{GapSVP}$ is only able to achieve an $2^{\Theta(n)}$-approximation, and any improvement on it w…

Let $P_n$ consist of $n$ independent random points uniformly distributed in $[0,1]^2$, and let a bipartite coloring of $P_n$ be any coloring induced by a Euclidean minimum spanning…