31 citations · 56 across the 21 of their papers we have counts for
34 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, ca…
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 -node graphs require integer variables. We prove that this is almost optimal: We give a family…
Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set
Karthekeyan Chandrasekaran, Chandra Chekuri, Samuel Fiorini +2
We consider the feedback vertex set problem in undirected graphs (FVS). The input to FVS is an undirected graph with non-negative vertex costs. The goal is to find a mini…