3 papers
cs.CC2025
Complexity of Firefighting on Graphs
Julius Althoetmar, Jamico Schade, Torben Schürenberg
We consider a pursuit-evasion game that describes the process of extinguishing a fire burning on the nodes of an undirected graph. We denote the minimum number of firefighters requ…
cs.DM2023
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…
math.CO2021
Lattice-free simplices with lattice width
Lukas Mayrhofer, Jamico Schade, Stefan Weltge
The Flatness theorem states that the maximum lattice width of a -dimensional lattice-free convex set is finite. It is the key ingredient for Lenstra's algorithm f…