34 problems

Let $S$ be a finite set of finite strings. For strings $x$ and $y$, let $\operatorname{ov}(x,y)$ be the maximum length of a string that is simultaneously a suffix of $x$ and a pref…

For every connected graph $G$, the broadcast domination number is at most twice the multipacking number: $\gamma_b(G)\leq 2\operatorname{mp}(G)$, where $\gamma_b(G)$ is the minimum…

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

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…

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

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.

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…

Let $P\subseteq\mathbb{R}^2$ be a finite point set. A bipartite coloring is obtained by choosing a Euclidean minimum spanning tree of $P$ and partitioning $P=R\cup B$ so that every…

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…

Priestley's conjecture. $k$-ECSM admits a polynomial-time $(1+O(1/k))$-approximation algorithm.

Let $m$ be the number of subsets, let $p$ be the inclusion probability, and let $n$ be the number of elements. Write $\operatorname{val}_{\mathrm{GR}}$ for the value produced by th…

Let $m$ be the number of subsets, let $p$ be the inclusion probability, and let $n$ be the number of elements. Write $\operatorname{val}_{\mathrm{GR}}$ for the value produced by th…

Let $m$ be the number of subsets, let $p$ be the inclusion probability, and let $n$ be the number of elements. Write $\operatorname{val}_{\mathrm{GR}}$ for the value produced by th…

Approximation-hardness conjecture. Unless P=NP, there is no $\alpha$-approximation algorithm for computing $\operatorname{sinv}_k(D)$ or $\operatorname{sinv}'_k(D)$.

Pseudodistribution product inequality.

Let sparse graphs have $m=\tilde{O}(n)$ edges, and consider the four variants obtained by choosing directed or undirected graphs and weighted or unweighted edges. For…

A cubic graph is a graph in which every vertex has degree three. Mohar's conjecture. Approximating the genus of cubic graphs is APX-hard. This conjecture asserts computational hard…

Let $H=(V,E)$ be a hypergraph, let $w\in\mathbb{R}_{\geq 0}^E$ be edge weights, and let $x\in[0,1]^E$ be a fractional matching, meaning that … where $\delta(v)=\\{e\in E:v\in e\\}$…

Consider the metric traveling salesperson problem and its subtour linear programming relaxation. A feasible solution is half-integral if every edge variable satisfies…

For each $m$, let $S_m$ be a star with $m$ children rooted at its centre vertex, chosen to maximise the length of the longest edge in the tree produced by the $(\delta,k)$-PKRY alg…

Six-fifths conjecture. If $x\in\mathrm{LP}(G)$, then $\frac{6}{5}x$ dominates a convex combination of 2-edge-connected multigraphs of $G$. Equivalently,

Approximation-ratio conjecture. The ratio satisfies

Let $d\geq 2$ be fixed, and let $\mathcal{G}\subset \mathrm{SU}(d)$ be a finite gate set that densely generates $\mathrm{SU}(d)$. An inverse-free Solovay–Kitaev theorem asserts tha…

Let $G$ range over graphs. For each $K\in\mathbb{N}$, let $\alpha_K$ denote the smallest $K$-asymptotic robustness ratio over all graphs, and let $\alpha^*(G)$ denote the randomize…