54 problems

Conjecture. There exist an absolute constant $c\ge 1$ and an online algorithm such that, for every finite matroid $M$ and every choice of nonnegative weights, the algorithm selects…

For every matroid $M=(E,\mathcal{I})$ and every nonnegative weight function $w:E\to\mathbb{R}_{\ge 0}$, when the elements of $E$ arrive in a uniformly random order and their weight…

Given a sequence of insertions of elements into a ground set, a monotone submodular function $f$ accessible through value queries, and a cardinality bound $k$, does there exist a r…

The conjecture asserts that there exists a polynomial $p(d,k)$ such that, for every $d,k\in\mathbb{Z}_{\ge 1}$ and every lattice polytope $P\subseteq[0,k]^d$, its monotone diameter…

Given a finite simple unweighted graph $G=(V,E)$, decide whether the standard Goemans–Williamson semidefinite relaxation of Max-Cut has the same optimal value as the integer Max-Cu…

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…

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

Recursive upper-bound conjecture. In a $d$-dimensional setting,

Feasible indexing conjecture. There exists an indexing satisfying this successor-set ordering and, whenever two consecutive nodes have equal successor-set order,

Weaker dijoin decomposition conjecture. The arc set $A$ can be decomposed into a $k$-dijoin and a $(\tau-k)$-dijoin, for every $k\in\{1,\ldots,\tau-1\}$.

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…

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…

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…

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

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 $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.

Taillard's conjecture. For a fixed number of machines $M$,

Let a quadratic assignment problem (QAP) instance be given, and suppose that a few assignments are identified as belonging to a high-quality solution. Consider permanently fixing t…

Quadratic-logarithmic lower-bound conjecture. There exist instances of the textsc{Pebble Motion Problem on Trees} for which the length of the shortest solution sequences is

Bounded-degeneracy conjecture. The limit

Let $M$ be a matroid on a ground set $E$, let $\Gamma$ be an abelian group, let $\psi\colon E\to\Gamma$ be a group labeling, let $F\subseteq\Gamma$ be a finite set, and let…