Abstract:For a set $X$ of integer points, the relaxation complexity $\operatorname{rc}(X)$ is the smallest number of facets of any polyhedron $P$ such that $P \cap \mathbb{Z}^d = X$. In this paper, we focus on the case where $X$ is the discrete standard simplex $\Delta_d = \{\mathbf{0}, \mathbf{e}_1, \dots, \mathbf{e}_d\}$. We show that $\operatorname{rc}(\Delta_d) = O(\log d)$ by an explicit, elementary construction. This improves upon the previously best-known upper bound $\operatorname{rc}(\Delta_d) = O(d / \sqrt{\log d})$ due to Aprile, Averkov, Di Summa, and Hojny (2024) and matches an asymptotic lower bound by Averkov and Schymura (2022).
From: Stefan Weltge [view email]
[v1]
Wed, 10 Jun 2026 09:30:03 UTC (6 KB)
[v2]
Wed, 8 Jul 2026 08:22:21 UTC (6 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。