Publications de Yuri Faenza | EPFL Graph Search

Extended Formulations from Communication Protocols in Output-Efficient Time

Deterministic protocols are well-known tools to obtain extended formulations, with many applications to polytopes arising in combinatorial optimization. Although constructive, those tools are not output-efficient, since the time needed to produce the exten ...

SPRINGER INTERNATIONAL PUBLISHING AG2019

A PTAS for the Time-Invariant Incremental Knapsack Problem, Combinatorial Optimization

Yuri Faenza, Igor Malinovic

2018

On Bounded Pitch Inequalities for the Min-Knapsack Polytope, Combinatorial Optimization

Ola Nils Anders Svensson, Yuri Faenza, Igor Malinovic

2018

On 2-Level Polytopes Arising In Combinatorial Settings

Yuri Faenza, Manuel Francesco Aprile, Alfonso Bolívar Cevallos Manzano

2-level polytopes naturally appear in several areas of pure and applied mathematics, including combinatorial optimization, polyhedral combinatorics, communication complexity, and statistics. In this paper, we present a study of some 2-level polytopes arisi ...

SIAM Publications2018

Extension complexity of stable set polytopes of bipartite graphs

Yuri Faenza, Manuel Francesco Aprile

The extension complexity xc(P) of a polytope P is the minimum number of facets of a polytope that affinely projects to P. Let G be a bipartite graph with n vertices, m edges, and no isolated vertices. Let STAB(G) be the convex hull of the stable sets of G. ...

Springer2017

On vertices and facets of combinatorial 2-level polytopes

Yuri Faenza, Manuel Francesco Aprile, Alfonso Bolívar Cevallos Manzano

2-level polytopes naturally appear in several areas of mathematics, including combinatorial optimization, polyhedral combinatorics, communication complexity, and statistics. We investigate upper bounds on the product of the number of facets and the number ...

Springer2016

On largest volume simplices and sub-determinants

Friedrich Eisenbrand, Yuri Faenza, Carsten Moldenhauer, Marco Di Summa

2015

Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition

Yuri Faenza, Gautier Stauffer

We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O(vertical bar V vertical bar (vertical bar E vertical bar+vertical bar V vertical bar log vertical bar V vertical bar))-time, drastically improvin ...

Assoc Computing Machinery2014

Solving the stable set problem in terms of the odd cycle packing number

Yuri Faenza, Carsten Moldenhauer, Andres Jacinto Ruiz Vargas, Adrian Aloysius Bock

2014

On The Convergence Of The Affine Hull Of The Chvatal-Gomory Closures

Yuri Faenza, Marco Di Summa

Given an integral polyhedron P subset of R-n and a rational polyhedron Q subset of R-n containing the same integer points as P, we investigate how many iterations of the Chvatal-Gomory closure operator have to be performed on Q to obtain a polyhedron conta ...

SIAM Publications2013