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

Igor Malinovic, Yuri Faenza

2018

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

Igor Malinovic, Ola Nils Anders Svensson, Yuri Faenza

2018

On 2-Level Polytopes Arising In Combinatorial Settings

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

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

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

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, Marco Di Summa, Carsten Moldenhauer, Yuri Faenza

2015

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

Gautier Stauffer, Yuri Faenza

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

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

2014

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

Marco Di Summa, Yuri Faenza

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

Extended Formulations, Nonnegative Factorizations, and Randomized Communication Protocols

Hans Raj Tiwary, Yuri Faenza

We show that the binary logarithm of the nonnegative rank of a nonnegative matrix is, up to small constants, equal to the minimum complexity of a randomized communication protocol computing the matrix in expectation. We use this connection to prove new con ...

Springer Berlin Heidelberg2012