S. Fiorini

activity

20072026

most citedExtended formulations for polygons

81 citations · 388 across the 46 of their papers we have counts for

collaborators

Showing 2020Show all

4 papers · 1 filter

math.CO2020

A simple $(2 + ε)$ -approximation algorithm for Split Vertex Deletion

Matthew Drescher, Samuel Fiorini, Tony Huynh

A split graph is a graph whose vertex set can be partitioned into a clique and a stable set. Given a graph $G$ and weight function $w : V (G) \to Q_{\geq 0}$ , the Split Vert…

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…

A simple (2+ε)-approximation algorithm for Split Vertex Deletion

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

A Tight Approximation Algorithm for the Cluster Vertex Deletion Problem

Recognizing Cartesian products of matrices and polytopes

A simple $(2 + ε)$ -approximation algorithm for Split Vertex Deletion