research
∙
06/24/2022
The role of rationality in integer-programming relaxations
For a finite set X ⊂ℤ^d that can be represented as X = Q ∩ℤ^d for some p...
share
research
∙
03/18/2022
Exact approaches for the Connected Vertex Cover problem
Given a graph G, the Connected Vertex Cover problem (CVC) asks to find a...
research
∙
06/24/2021
Slack matrices, k-products, and 2-level polytopes
In this paper, we study algorithmic questions concerning products of mat...
research
∙
06/23/2021
Extended formulations for matroid polytopes through randomized protocols
Let P be a polytope. The hitting number of P is the smallest size of a h...
research
∙
06/22/2021
Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
Let G be a connected n-vertex graph in a proper minor-closed class 𝒢. We...
research
∙
06/01/2021
Binary extended formulations and sequential convexification
A binarization of a bounded variable x is a linear formulation with vari...
research
∙
08/20/2020
A simple 7/3-approximation algorithm for feedback vertex set in tournaments
We show that performing just one round of the Sherali-Adams hierarchy gi...
research
∙
07/16/2020
A Tight Approximation Algorithm for the Cluster Vertex Deletion Problem
We give the first 2-approximation algorithm for the cluster vertex delet...
research
∙
02/06/2020
Recognizing Cartesian products of matrices and polytopes
The 1-product of matrices S_1 ∈R^m_1 × n_1 and S_2 ∈R^m_2 × n_2 is the m...
research
∙
09/18/2019
Regular matroids have polynomial extension complexity
We prove that the extension complexity of the independence polytope of e...
research
∙
11/20/2018