Polynomial-time recognition conjecture for 0/1 slack matrices
Polynomial-time recognition conjecture for 0/1 slack matrices
Let . A matrix is a slack matrix if it is the slack matrix of a polytope. Polynomial-time recognition conjecture. There is an algorithm polynomial in that correctly determines whether is the slack matrix of a polytope. The conjecture concerns the unresolved complexity of recognizing slack matrices among 0/1-valued matrices, equivalently the recognition problem for 2-level polytopes.
Sources & referencesView supporting material
Primary source
Manuel Aprile, Michele Conforti, Yuri Faenza, Samuel Fiorini, Tony Huynh and Marco Macchia, “Slack matrices, k-products, and 2-level polytopes”, arXiv:2106.12829 (2021).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.