2021/04/29 by Matthias Brugger, Brugger, Matthias, Α. Schulz +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #History and Theory of Mathematics #Mathematics and Applications #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2104.14486
openalex publication_date 2021/04/29 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
The 0,\(1)/(2) -closure of a rational polyhedron x colon Ax \≤\nb is obtained by adding all Gomory-Chv 'atal cuts that can be derived from\nthe linear system Ax \≤ b using multipliers in 0,\(1)/(2) . We show\nthat deciding whether the 0,\(1)/(2) -closure coincides with the\ninteger hull is strongly NP-hard. A direct consequence of our proof is that,\ntesting whether the linear description of the 0,\(1)/(2) -closure\nderived from Ax \≤ b is totally dual integral, is strongly NP-hard.\n