Showing 2026Show all
2 papers · 1 filter
math.OC2026
Hardness of some optimization problems over correlation polyhedra
Alberto Caprara, Fabio Furini, Claudio Gentile +2
We prove the \textbf{NP}-hardness, using Karp reductions, of some problems related to the correlation polytope and its corresponding cone, spanned by all of the rank-on…
cs.CC2026
On Saxe's theorems about the complexity of the Distance Geometry Problem
Maël Kupperschmitt, Leo Liberti
In 1979, James B.~Saxe published an extended summary on the complexity of the Distance Geometry Problem in the proceedings of the 17th Allerton Conference. Many of the proofs in hi…