Stefan Weltge

collaborators

Showing cs.DMShow all

2 papers · 1 filter

cs.DM2026

The relaxation complexity of the standard simplex is logarithmic

Gennadiy Averkov, Simon Keil, Stefan Weltge

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 \cap Z^{d} = X$ . In thi…

cs.DM2024

Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack

Jamico Schade, Makrand Sinha, Stefan Weltge

Standard mixed-integer programming formulations for the stable set problem on $n$ -node graphs require $n$ integer variables. We prove that this is almost optimal: We give a family…