Personne

Yuri Faenza

Cette personne n’est plus à l’EPFL

Publications associées (12)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

Extended Formulations from Communication Protocols in Output-Efficient Time

Yuri Faenza, Manuel Francesco Aprile

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

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

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

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

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

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

In this paper, we provide the first linear programming formulations for the stable set problem in claw-free graphs, together with polynomial time separation routines for those formulations (they are not compact). We then exploit one of those extended formu ...

2012

We deal with some generalizations of the graph coloring problem on classes of perfect graphs. Namely we consider the μ-coloring problem (upper bounds for the color on each vertex), the precoloring extension problem (a subset of vertices colored beforehand) ...

Elsevier2012

We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O(n^3)-time, drastically improving the previous best known complexity bound. This algorithm is based on a novel decomposition theorem for claw-free ...

2011