68 citations · 142 across the 43 of their papers we have counts for
7 papers · 1 filter
Simple Random Order Contention Resolution for Graphic Matroids with Almost no Prior Information
Richard Santiago, Ivan Sergeev, Rico Zenklusen
Random order online contention resolution schemes (ROCRS) are structured online rounding algorithms with numerous applications and links to other well-known online selection proble…
Congruency-Constrained TU Problems Beyond the Bimodular Case
Martin Nägele, Richard Santiago, Rico Zenklusen
A long-standing open question in Integer Programming is whether integer programs with constraint matrices with bounded subdeterminants are efficiently solvable. An important specia…
Extension complexities of Cartesian products involving a pyramid
Hans Raj Tiwary, Stefan Weltge, Rico Zenklusen
It is an open question whether the linear extension complexity of the Cartesian product of two polytopes P, Q is the sum of the extension complexities of P and Q. We give an affirm…
Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations
Robert Hildebrand, Robert Weismantel, Rico Zenklusen
We prove that any mixed-integer linear extended formulation for the matching polytope of the complete graph on vertices, with a polynomial number of constraints, requires $Ω(\s…
Sublinear Bounds for a Quantitative Doignon-Bell-Scarf Theorem
Stephen R. Chestnut, Robert Hildebrand, Rico Zenklusen
The recent paper "A quantitative Doignon-Bell-Scarf Theorem" by Aliev et al. generalizes the famous Doignon-Bell-Scarf Theorem on the existence of integer solutions to systems of l…
Interdicting Structured Combinatorial Optimization Problems with {0,1}-Objectives
Stephen R. Chestnut, Rico Zenklusen
Interdiction problems ask about the worst-case impact of a limited change to an underlying optimization problem. They are a natural way to measure the robustness of a system, or to…
Mixed Integer Reformulations of Integer Programs and the Affine TU-dimension of a Matrix
Jörg Bader, Robert Hildebrand, Robert Weismantel +1
We study the reformulation of integer linear programs by means of a mixed integer linear program with fewer integer variables. Such reformulations can be solved efficiently with mi…