3 papers
math.OC2023
On the Number of Degenerate Simplex Pivots
Kirill Kukharenko, Laura Sanità
The simplex algorithm is one of the most popular algorithms to solve linear programs (LPs). Starting at an extreme point solution of an LP, it performs a sequence of basis exchange…
math.CO2023
Polytope Extensions with Linear Diameters
Volker Kaibel, Kirill Kukharenko
We describe constructions of extended formulations that establish a certain relaxed version of the Hirsch conjecture and prove that if there is a pivot rule for the simplex algorit…
math.CO2020
Scale-free spanning trees: complexity, bounds and algorithms
Yury Orlovich, Kirill Kukharenko, Volker Kaibel +1
We introduce and study the general problem of finding a most "scale-free-like" spanning tree of a connected graph. It is motivated by a particular problem in epidemiology, and may…