125 problems

Frame–Stewart conjecture. This recurrence equals the true optimum for every $n$. The conjecture asserts optimality of the standard divide-and-conquer strategy for the four-peg Towe…

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…

Let $G(k)$ be the length of an optimal Golomb ruler with $k$ marks. Singer-type upper-bound conjecture. For every integer $k\geq6$, … The source derives this as a consequence of th…

Let $\mathcal{S}_1$ and $\mathcal{S}_2$ be sets of integers with the same set of pairwise differences $\mathcal{D}$, and suppose that every pairwise difference in $\mathcal{D}$ is…

Reciprocal-integer deficiency conjecture. There exists an $m\in\mathbb{N}$ such that

Complete-graph degree sequence optimization conjecture. The line sum problem over $H=K_{m,n}$, as well as the degree sequence optimization problem over $H=K_n$, is polynomial-time…

Let $k,n$ be positive integers. For each $j\in\{1,\ldots,k\}$, let $S_j$ be the collection of subsets $L\subseteq[n]^k$ such that $|L|=n$ and no two distinct elements of $L$ have t…

Let $A$ be a $\{0,1\}$-matrix whose columns each contain the same number $d\geq 2$ of $1$'s, with column vectors $v_1,\ldots,v_q$. Let $\mathcal{C}$ be the clutter associated with…

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…

Fix $c>0$ and let $G(n,cn)$ be the sparse random graph with $n$ vertices and $cn$ edges. Let an object be one of the graph optimization objects discussed in the source, such as an…

Automatic optimization conjecture. Similar schemes should prove useful for optimizing ILS algorithms in a nearly automatic way.

Finite exact-density tile-family conjecture. For every fixed $q$, there is a finite coordinate-symmetric family of induced templates of independence density $1/q$ such that, in eve…

Equality conjecture. The two quantities coincide exactly:

Let ${\mathcal G}'(k,n)$ be the collection of graphs whose vertices are labeled by $k$-subsets of an $n$-element set, with the property that for vertices labeled by $S$ and $T$, th…

The standard penalty-encoded QUBO approach submits both an objective and constraint penalties to a sparse-topology quantum processing unit (QPU), while a penalty-free approach samp…

Extremal polymatroid $a$-reducedness conjecture. The polymatroid $f$ is actually $a$-reduced; consequently,

Let $k\geq 4$, and let $\delta^*(k)$ denote the optimal balanced discrepancy for the module-lattice sign-selection problem. Write $\delta^*$ for the constant value proposed by the…

MF-AOA asymptotic performance conjecture. In the limit $n\rightarrow\infty$, AMP algorithms such as the MF-AOA achieve a performance of approximately

Consider the complete graph $K_n$ with vertices ordered $1,\ldots,n$, whose edges are ordered lexicographically and whose $i$-th edge has weight $r^{N-i}$, where $N=\binom{n}{2}$ a…

Let $d\ge 3$, let $p\ge 1$, and consider two independent point clouds $X_1,\ldots,X_n$ and $Y_1,\ldots,Y_n$ sampled uniformly from $[0,1]^d$. A matching $\sigma_p$ is $p$-optimal i…

Let $F_{k,m,n}(t)=\mathbb{E}(\exp(t\cdot C_{k,m,n}))$ be the moment generating function of the minimum cost $C_{k,m,n}$ of a $k$-matching in the random bipartite matching model. Ze…

Let $C_{k,m,n}$ be the minimum cost of a $k$-matching in the random bipartite matching model, and let its cumulants $\kappa_p$ be defined by … where…

Bounded-entry tree integer-programming conjecture. The integer program can be solved in polynomial time for constant $d$.

Totally $\Delta$-modular integer-program conjecture. For any constant $\Delta$, this integer program can be solved in polynomial time when $A$ is totally $\Delta$-modular.

Let $B_1,\dots,B_k$ be the bases and let $T_1,\dots,T_\ell$ be pairwise disjoint sets in the setting of the source's equitability theorem. Akrami–Raj–Végh equitability conjecture.…