4 problems

For each integer $m\geq 2$, consider the integer program $(\mathrm{CE})_m$ with variables $x\in\{0,1\}^{2m}$ and its linear relaxation. Let $x_m^\circ$ denote an optimal solution o…

Consider an instance of the multiple knapsack problem with compacity constraints, its linear relaxation $(\mathrm{mKPC})_{\mathrm{LP}}$, and its naive semidefinite relaxation. Writ…

Let $F$ be Thompson's group, with finite presentation … The complexity conjecture for Thompson's group $F$. The knapsack problem for $F$ is in fact $\Sigma^2_p$-complete. The paper…

Let $\boldsymbol a\in\mathbb Z^n$ be an arbitrary integer vector, let $b\in\mathbb Z$, and consider the knapsack feasibility problem … Write $\|\boldsymbol x\|_0$ for the number of…