
Slack matrices, kproducts, and 2level polytopes
In this paper, we study algorithmic questions concerning products of mat...
read it

Smaller extended formulations for spanning tree polytopes in minorclosed classes and beyond
Let G be a connected nvertex graph in a proper minorclosed class 𝒢. We...
read it

Integer programs with bounded subdeterminants and two nonzeros per row
We give a strongly polynomialtime algorithm for integer linear programs...
read it

A simple (2+ε)approximation algorithm for Split Vertex Deletion
A split graph is a graph whose vertex set can be partitioned into a cliq...
read it

A simple 7/3approximation algorithm for feedback vertex set in tournaments
We show that performing just one round of the SheraliAdams hierarchy gi...
read it

A Tight Approximation Algorithm for the Cluster Vertex Deletion Problem
We give the first 2approximation algorithm for the cluster vertex delet...
read it

Recognizing Cartesian products of matrices and polytopes
The 1product of matrices S_1 ∈R^m_1 × n_1 and S_2 ∈R^m_2 × n_2 is the m...
read it

Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
Let G be an nnode graph without two disjoint odd cycles. The algorithm ...
read it

Regular matroids have polynomial extension complexity
We prove that the extension complexity of the independence polytope of e...
read it

Unavoidable minors for graphs with large ℓ_pdimension
A metric graph is a pair (G,d), where G is a graph and d:E(G) →R_≥0 is a...
read it

Improved approximation algorithms for hitting 3vertex paths
We study the problem of deleting a minimum cost set of vertices from a g...
read it

Bounds on the number of 2level polytopes, cones and configurations
We prove an upper bound of the form 2^O(d^2 polylog d) on the number of ...
read it

Extension Complexity of the Correlation Polytope
We prove that for every nvertex graph G, the extension complexity of th...
read it

Strengthening Convex Relaxations of 0/1Sets Using Boolean Formulas
In convex integer programming, various procedures have been developed to...
read it

A tight ErdősPósa function for wheel minors
Let W_t denote the wheel on t+1 vertices. We prove that for every intege...
read it
Samuel Fiorini
is this you? claim profile