NP-hardness of maximal angle computation for the nonnegative orthant
NP-hardness of maximal angle computation for the nonnegative orthant
Let be a polyhedral cone, and let denote the problem of computing the maximal angle between cones and . Orthant-restriction conjecture. Computing the maximal angle between and a polyhedral cone is NP-hard, that is, solving is NP-hard. The preceding result establishes NP-hardness when the first cone is generated by a subset of the canonical basis; the conjecture asks whether NP-hardness persists when the first cone is the full nonnegative orthant.
Sources & referencesView supporting material
Primary source
Giovanni Barbarino, Nicolas Gillis and David Sossa, “Computing cone-constrained singular values of matrices”, arXiv:2504.04069 (2026).
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.