6 problems

MIRUP conjecture. The Modified Integer Round Up Property holds for all instances of the CSP and BPP.

Epstein and van Stee's conjecture. The asymptotic performance ratio of online bounded-space $d$-CPP is $\Theta(\log d)$. Epstein and van Stee established the bounds…

Let $(s,b)$ be a Bin Packing instance with item sizes $s_1,\ldots,s_n\in[0,1]$, and let $OPT_f$ denote the optimal value of the Gilmore–Gomory LP relaxation. The integrality-gap co…

Consider the one-dimensional minimax bin-packing problem with bin size constraints, restricted to the special case of two bins. Brusco–Köhn–Steinley conjecture. This two-bin specia…

Scheithauer's conjecture. The general one-dimensional cutting stock problem has the modified integer round-up property.

Let $s=(s_1,\dots,s_n)$ be item sizes, let $\mathcal{P}=\{p\in\{0,1\}^n:s^Tp\leq 1\}$ be the feasible bin patterns, and let $OPT$ and $OPT_f$ denote the optimal integer and fractio…