Manuel Aprile

activity

20182021

collaborators

7 papers

cs.DM2021

Slack matrices, $k$ -products, and $2$ -level polytopes

Manuel Aprile, Michele Conforti, Yuri Faenza +3

In this paper, we study algorithmic questions concerning products of matrices and their consequences for recognition algorithms for polyhedra. The 1-product of matrices $S_{1}$ , $S_2…

math.CO2021

Extended formulations for matroid polytopes through randomized protocols

Manuel Aprile

Let $P$ be a polytope. The hitting number of $P$ is the smallest size of a hitting set of the facets of $P$ , i.e., a subset of vertices of $P$ such that every facet of $P$ has a ve…

math.OC2021

Binary extended formulations and sequential convexification

Manuel Aprile, Michele Conforti, Marco Di Summa

A binarization of a bounded variable $x$ is a linear formulation with variables $x$ and additional binary variables $y_{1}, \dots, y_{k}$ , so that integrality of $x$ is implied by the i…

math.CO2020

A simple 7/3-approximation algorithm for feedback vertex set in tournaments

Manuel Aprile, Matthew Drescher, Samuel Fiorini +1

We show that performing just one round of the Sherali-Adams hierarchy gives an easy 7/3-approximation algorithm for the Feedback Vertex Set (FVST) problem in tournaments. This matc…

math.CO2020

Recognizing Cartesian products of matrices and polytopes

Manuel Aprile, Michele Conforti, Yuri Faenza +3

The 1-product of matrices $S_{1} \in R^{m_{1} \times n_{1}}$ and $S_{2} \in R^{m_{2} \times n_{2}}$ is the matrix in $R^{(m_{1} + m_{2}) \times (n_{1} n_{2})}$ whose columns ar…

math.CO2019

Regular matroids have polynomial extension complexity

Manuel Aprile, Samuel Fiorini

We prove that the extension complexity of the independence polytope of every regular matroid on $n$ elements is $O (n^{6})$ . Past results of Wong and Martin on extended formulations o…