The relaxation complexity of the standard simplex is logarithmic

2026/06/10 by Gennadiy Averkov, Simon Keil, Stefan Weltge · 1 voice
Computer Science · Mathematics · #cs.DM #math.CO #math.OC

paper · pdf

arxiv published 2026/06/10 · arxiv updated 2026/07/08

Abstract

For a set X of integer points, the relaxation complexity rc(X) is the smallest number of facets of any polyhedron P such that P ∩ ℤ^d = X. In this paper, we focus on the case where X is the discrete standard simplex Δ_d = \0, e₁, …, e_d\. We show that rc(Δ_d) = O(log d) by an explicit, elementary construction. This improves upon the previously best-known upper bound rc(Δ_d) = O(d / √(log d)) due to Aprile, Averkov, Di Summa, and Hojny (2024) and matches an asymptotic lower bound by Averkov and Schymura (2022).

Citations

• The role of rationality in integer-programming relaxations
• Efficient MIP Techniques for Computing the Relaxation Complexity
• Computational Aspects of Relaxation Complexity: Possibilities and Limitations
• Improved lower bound on the dimension of the EU council's voting rules
• Complexity of linear relaxations in integer programming
• Lower Bounds on the Sizes of Integer Programs Without Additional Variables

Discussions

• Simon Keil, Stefan Weltge: The relaxation complexity of the standard simplex is logarithmic https://arxiv.org/abs/2606.11852 https://arxiv.org/pdf/2606.11852 https://arxiv.org/html/2606.11852 [bsky, 0 points, 0 comments]

Related

• Computational Aspects of Relaxation Complexity: Possibilities and Limitations
• Complexity of linear relaxations in integer programming
• The role of rationality in integer-programming relaxations
• Lower Bounds on the Sizes of Integer Programs Without Additional Variables
• Efficient MIP Techniques for Computing the Relaxation Complexity