Counterexample conjecture to the ROAD property for compact knapsack instances
Counterexample conjecture to the ROAD property for compact knapsack instances
For each integer , consider the integer program with variables and its linear relaxation. Let denote an optimal solution of that linear relaxation, and define
The ROAD property means that this matrix is feasible for the naive semidefinite relaxation. Counterexample conjecture. For all , there is an optimal solution of the linear relaxation for which there exist with such that
In particular, is not a solution of the naive semidefinite relaxation, and does not have the ROAD property. The supplied status evidence disproves this conjecture, so the asserted universal failure has a counterexample; the exact refutation is not specified in the provided material.
Sources & referencesView supporting material
Primary source
Hubert Villuendas, Mathieu Besançon and Jérôme Malick, “Knapsack with compactness: a semidefinite approach”, arXiv:2504.17543 (2025).
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.