80 problems

Let $I_A$ be a toric ideal, and let the true degree of a circuit of $A$ mean the degree computed without dividing by the common factor $c$ in the circuit formula. Sturmfels's conje…

A valid function is a function $\pi:\mathbb{R}\to\mathbb{R}_+$ satisfying the conditions for validity in the infinite group relaxation, and an extreme function is a valid function…

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 $L$ be the set of candidate cliques generated for a graph, and let valid zones satisfy the convexity property in Definition. Consider sufficiently regular graphs, such as unifo…

Let $(H_n)_{n\in\mathbb{N}_{\geq 1}}$ be a family of trees, and let $K_n$ denote the complete graph on $n$ vertices. Write $\operatorname{MT}(H_n,K_n)$ for the minimum number of st…

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…

The column number functions $\operatorname{g}(\Delta,r)$, $\operatorname{s}(\Delta,r)$, and $\operatorname{h}(\Delta,r)$ exhibit erratic behavior when one parameter is fixed and th…

Polynomial-time solvability conjecture. Integer programs with the incidence matrices of disjoint hypergraphs as constraint matrices should be solvable in polynomial time, even when…

Let the setting of Theorem be given, concerning the removal of interiors of closed convex sets in the paper's boundary hyperplane cover framework. Strictly convex boundary hyperpla…

Let $B=\{\mathbf{x}:\|\mathbf{x}\|_2\leq 1\}$ and $C=\{\mathbf{x}:g(\mathbf{x})\leq 0\}$, where $g$ is a quadratic polynomial. Suppose that $g$ has one of the forms … or … where…

Distance-reducing inclusion conjecture. For every matrix $A$,

Asymptotic maximal-prime conjecture. For all $\mathfrak{p}\in\operatorname{Max}^\infty(I)$, one has

Bounded-subdeterminant solvability conjecture. The integer program

Integer-programming conjecture. For every fixed $\Delta$, (IP) can be solved in polynomial time whenever $\mathbf{A}$ is $\Delta$-modular.

Fixed-$\Delta$ tractability conjecture. There is a polynomial-time algorithm to solve any integer program of the form (IP) with a $\Delta$-modular constraint matrix.

Consider the cutting stock instances in the classes discussed in the source, their relaxation polyhedron, and the convex hull of their integer solutions. The near-integral relaxati…

In the cutting stock problem, let an AI instance be an instance from the AI class, and let its relaxation have a polyhedron integrality ratio measuring the closeness of the relaxat…

Let $\Lambda\subset\mathbb{R}^d$ be a full-dimensional lattice, and let $\mathrm{Flt}(d)$ be the least constant such that every convex body $C\subset\mathbb{R}^d$ with…

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

Ahanjideh–Ekim–Yıldız conjecture. For all natural numbers $d\geq 2$ and $m$, we have

Subspace Flatness Conjecture. One has

Linear lattice-width conjecture. The lattice width can be bounded by a function which depends only linearly on $n$. The currently known upper bound is $\mathcal{O}^{*}(n^{4/3})$, s…

Let $\ve A\in\mathbb{Z}^{m\times n}$, let $\ve b\in\mathbb{Z}^{m}$, and let $\ve c\in\mathbb{Q}^{n}$. Consider the linear relaxation $\operatorname{LP}(\ve A,\ve b,\ve c)$ and the…