81 citations · 388 across the 46 of their papers we have counts for
4 papers · 1 filter
Average case polyhedral complexity of the maximum stable set problem
Gábor Braun, Samuel Fiorini, Sebastian Pokutta
We study the minimum number of constraints needed to formulate random instances of the maximum stable set problem via linear programs (LPs), in two distinct models. In the uniform…
Generalised probabilistic theories and conic extensions of polytopes
Samuel Fiorini, Serge Massar, Manas K. Patra +1
Generalized probabilistic theories (GPT) provide a general framework that includes classical and quantum theories. It is described by a cone and its dual . We show that wh…
Uncapacitated Flow-based Extended Formulations
Samuel Fiorini, Kanstantsin Pashkovich
An extended formulation of a polytope is a linear description of this polytope using extra variables besides the variables in which the polytope is defined. The interest of extende…
The Price of Connectivity for Vertex Cover
Eglantine Camby, Jean Cardinal, Samuel Fiorini +1
The vertex cover number of a graph is the minimum number of vertices that are needed to cover all edges. When those vertices are further required to induce a connected subgraph, th…