Manuel Aprile

activity

20182026

collaborators

Showing math.COShow all

7 papers · 1 filter

math.CO2026

The red-blue-yellow matching problem

Manuel Aprile, Marco Di Summa

We consider the red-blue-yellow matching problem: given two natural numbers $k_{R}$ , $k_{B}$ and a graph $G$ whose edges are colored red, blue or yellow, the goal is to find a matching…

math.CO2024

Integer programs with nearly totally unimodular matrices: the cographic case

Manuel Aprile, Samuel Fiorini, Gwenaël Joret +4

It is a notorious open question whether integer programs (IPs), with an integer coefficient matrix $M$ whose subdeterminants are all bounded by a constant $Δ$ in absolute value, ca…

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.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…