research
∙
08/31/2023
Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack
Standard mixed-integer programming formulations for the stable set probl...
share
research
∙
03/22/2023
Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set
We consider the feedback vertex set problem in undirected graphs (FVS). ...
research
∙
02/16/2022
The Pareto cover problem
We introduce the problem of finding a set B of k points in [0,1]^n such ...
research
∙
06/10/2021
Integer programs with bounded subdeterminants and two nonzeros per row
We give a strongly polynomial-time algorithm for integer linear programs...
research
∙
06/08/2021
Lifts for Voronoi cells of lattices
Many polytopes arising in polyhedral combinatorics are linear projection...
research
∙
11/17/2020
Simple Iterative Methods for Linear Optimization over Convex Sets
We give simple iterative methods for computing approximately optimal pri...
research
∙
08/17/2020
Binary scalar products
Let A,B ⊆ℝ^d both span ℝ^d such that ⟨ a, b ⟩∈{0,1} holds for all a ∈ A,...
research
∙
03/25/2020
Improved lower bound on the dimension of the EU council's voting rules
Kurz and Napel (2015) proved that the voting system of the EU council (b...
research
∙
11/27/2019
Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
Let G be an n-node graph without two disjoint odd cycles. The algorithm ...
research
∙
11/25/2019
Minimum-cost integer circulations in given homology classes
Let D be a directed graph cellularly embedded on a surface together with...
research
∙
11/04/2019
Persistency of Linear Programming Formulations for the Stable Set Problem
The Nemhauser-Trotter theorem states that the standard linear programmin...
research
∙
08/17/2019
The stable set problem in graphs with bounded genus and bounded odd cycle packing number
Consider the family of graphs without k node-disjoint odd cycles, where ...
research
∙
05/25/2018
Extended Formulations for Radial Cones
This paper studies extended formulations for radial cones at vertices of...
research
∙
12/06/2017
Lifting Linear Extension Complexity Bounds to the Mixed-Integer Setting
Mixed-integer mathematical programs are among the most commonly used mod...
research
∙
11/03/2017