Manuel Aprile

activity

20172026

most citedSmaller extended formulations for spanning tree polytopes in minor-closed classes and beyond

7 citations · 12 across the 12 of their papers we have counts for

collaborators

Showing 2020Show all

3 papers · 1 filter

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

A Tight Approximation Algorithm for the Cluster Vertex Deletion Problem

Manuel Aprile, Matthew Drescher, Samuel Fiorini +1

We give the first $2$ -approximation algorithm for the cluster vertex deletion problem. This is tight, since approximating the problem within any constant factor smaller than $2$ is…

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…