Marco Macchia

activity

20172021

most citedExtension complexity of stable set polytopes of bipartite graphs

4 citations · 4 across the 5 of their papers we have counts for

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

The biclique covering number of grids

Krystal Guo, Tony Huynh, Marco Macchia

We determine the exact value of the biclique covering number for all grid graphs.

math.CO2018

Bounds on the number of 2-level polytopes, cones and configurations

Samuel Fiorini, Marco Macchia, Kanstantsin Pashkovich

We prove an upper bound of the form $2^{O (d^{2} polylog d)}$ on the number of affine (resp. linear) equivalence classes of, by increasing order of generality, 2-level d-pol…

cs.DM2018

Extension Complexity of the Correlation Polytope

Pierre Aboulker, Samuel Fiorini, Tony Huynh +2

We prove that for every $n$ -vertex graph $G$ , the extension complexity of the correlation polytope of $G$ is $2^{O (tw (G) + l o g n)}$ , where $tw (G)$ is the treewid…

math.CO2017

Enumeration of $2$ -level polytopes

Adam Bohn, Yuri Faenza, Samuel Fiorini +3

A (convex) polytope $P$ is said to be $2$ -level if for every direction of hyperplanes which is facet-defining for $P$ , the vertices of $P$ can be covered with two hyperplanes of th…