The Computational Complexity of Integer Programming with Alternations

DOI10.1287/MOOR.2018.0988zbMath1437.90107OpenAlexW2966775917WikidataQ127409955 ScholiaQ127409955MaRDI QIDQ5108263

Danny Nguyen, Igor Pak

Publication date: 30 April 2020

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7515/

zbMATH Keywords

computational complexityinteger programmingprogrammingtheoryintegeralternationsprojection of integer points

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

On the complexity of robust multi-stage problems with discrete recourse

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Integer points in polyhedra
• Triangulations. Structures for algorithms and applications
• Subclasses of Presburger arithmetic and the polynomial-time hierarchy
• Lattice translates of a polytope and the Frobenius problem
• Geometric algorithms and combinatorial optimization
• Complexity of Presburger arithmetic with fixed quantifier dimension
• Integer Programming with a Fixed Number of Variables
• COMPLEXITY OF SHORT GENERATING FUNCTIONS
• Integer Programming and Algorithmic Geometry of Numbers
• New Hardness Results for Diophantine Approximation
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• Short rational generating functions for lattice point problems
• Complexity of short Presburger arithmetic
• Computational Complexity
• Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials
• Minimizing the number of lattice points in a translated polygon

This page was built for publication: The Computational Complexity of Integer Programming with Alternations