4 papers
The relaxation complexity of the standard simplex is logarithmic
Gennadiy Averkov, Simon Keil, Stefan Weltge
For a set of integer points, the relaxation complexity is the smallest number of facets of any polyhedron such that . In thi…
Coloring t-perfect graphs with fewer colors
Matija NovakoviÄ, Stefan Weltge
Recently, Chudnovsky, Cook, Davies, Oum, and Tan obtained the first finite bound on the chromatic number of t-perfect graphs, showing that they are 199053-colorable. We improve thi…
On the number of finite additive 2-bases
Stefan Weltge, Konrad Zyhalko
The number of finite additive 2-bases is known to grow exponentially. While this fact has been established by Marzuola and Miller (2010) using complex analytic techniques embedded…
Integer programs with nearly totally unimodular matrices: the cographic case
Manuel Aprile, Samuel Fiorini, Gwenaël Joret +4
It is a notorious open question whether integer programs (IPs), with an integer coefficient matrix whose subdeterminants are all bounded by a constant in absolute value, c…