7 citations · 12 across the 12 of their papers we have counts for
15 papers
The red-blue-yellow matching problem
Manuel Aprile, Marco Di Summa
We consider the red-blue-yellow matching problem: given two natural numbers , and a graph whose edges are colored red, blue or yellow, the goal is to find a matching…
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 whose subdeterminants are all bounded by a constant in absolute value, ca…
The role of rationality in integer-programming relaxations
Manuel Aprile, Gennadiy Averkov, Marco Di Summa +1
For a finite set that can be represented as for some polyhedron , we call a relaxation of and define the relaxation co…
Exact approaches for the Connected Vertex Cover problem
Manuel Aprile
Given a graph , the Connected Vertex Cover problem (CVC) asks to find a minimum cardinality vertex cover of that induces a connected subgraph. In this paper we describe some…
Slack matrices, -products, and -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_2…
Extended formulations for matroid polytopes through randomized protocols
Manuel Aprile
Let be a polytope. The hitting number of is the smallest size of a hitting set of the facets of , i.e., a subset of vertices of such that every facet of has a ve…
Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
Manuel Aprile, Samuel Fiorini, Tony Huynh +2
Let be a connected -vertex graph in a proper minor-closed class . We prove that the extension complexity of the spanning tree polytope of is . Th…
Binary extended formulations and sequential convexification
Manuel Aprile, Michele Conforti, Marco Di Summa
A binarization of a bounded variable is a linear formulation with variables and additional binary variables , so that integrality of is implied by the i…
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…
A Tight Approximation Algorithm for the Cluster Vertex Deletion Problem
Manuel Aprile, Matthew Drescher, Samuel Fiorini +1
We give the first -approximation algorithm for the cluster vertex deletion problem. This is tight, since approximating the problem within any constant factor smaller than is…
Recognizing Cartesian products of matrices and polytopes
Manuel Aprile, Michele Conforti, Yuri Faenza +3
The 1-product of matrices and is the matrix in whose columns ar…
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 elements is . Past results of Wong and Martin on extended formulations o…
Extended formulations from communication protocols in output-efficient time
Manuel Aprile, Yuri Faenza
Deterministic protocols are well-known tools to obtain extended formulations, with many applications to polytopes arising in combinatorial optimization. Although constructive, thos…
Extension complexity of stable set polytopes of bipartite graphs
Manuel Aprile, Yuri Faenza, Samuel Fiorini +2
The extension complexity of a polytope is the minimum number of facets of a polytope that affinely projects to . Let be a bipartite graph with verti…
On 2-level polytopes arising in combinatorial settings
Manuel Aprile, Alfonso Cevallos, Yuri Faenza
2-level polytopes naturally appear in several areas of pure and applied mathematics, including combinatorial optimization, polyhedral combinatorics, communication complexity, and s…