35 problems
Let be a bounded rational polytope, let denote its binary encoding length, and let . For…
For which integers does there exist a finite simple -regular graph such that, for every vertex , the triangle-degree…
This entry tracks Basu–Conforti–Di Summa–Jiang split-rank conjecture. It resolves a conjecture about split-cut complexity with an explicit quantitative guarantee. Latest developmen…
This entry tracks Gomory corner polyhedron edge-count problem. It gives the first progress beyond the standard vertex-pair estimate. Latest development The edge-count bound becomes…
Let be an integer matrix with columns , let … and set . L…
Let be a matrix of rank . The Gröbner fan of is the fan whose cones encode the reduced Gröbner bases of the toric ideal associated to . Sturmfel…
Bounded-entry tree integer-programming conjecture. The integer program can be solved in polynomial time for constant .
Totally -modular integer-program conjecture. For any constant , this integer program can be solved in polynomial time when is totally -modular.
Let be a toric ideal, and let the true degree of a circuit of mean the degree computed without dividing by the common factor in the circuit formula. Sturmfels's conje…
For each integer , consider the integer program with variables and its linear relaxation. Let denote an optimal solution o…
Consider an instance of the multiple knapsack problem with compacity constraints, its linear relaxation , and its naive semidefinite relaxation. Writ…
Let and , where is a quadratic polynomial. Suppose that has one of the forms … or … where…
Distance-reducing inclusion conjecture. For every matrix ,
Asymptotic maximal-prime conjecture. For all , one has
Fixed- tractability conjecture. There is a polynomial-time algorithm to solve any integer program of the form (IP) with a -modular constraint matrix.
Ahanjideh–Ekim–Yıldız conjecture. For all natural numbers and , we have
Let be a rational linear subspace. For , a conformal circuit decomposition is a representation of as a sum of conformal circuit vectors. A ve…
Finite-certificate conjecture. There exists a finite set such that
Let be the set of integer cutting patterns for the cutting stock problem, let denote the number of copies of item in pattern , and let be the demand…
Let be fixed. For a rational polyhedron , define the -dimensional projection closure by … where is the family of -dim…
Let and . For a rational polyhedron , let be its -halfspace closure, and let … where is the family…
Let be fixed. For a rational polyhedron , define the -halfspace closure by … where denotes the integer hull of . Polyhedrality conjecture for the…
Seymour's quarter-integral packing conjecture. Every ideal clutter has a -integral packing of value .
Non-idealness conjecture. There exists an integer such that every -wise intersecting clutter is non-ideal.
Let be the vertex set of a discretizable distance geometry problem, let assign vertices to ranks, and let denote the number of nodes at the ra…