Publications associées à Polyhedral combinatorics

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

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

On some problems related to 2-level polytopes

Manuel Francesco Aprile

In this thesis we investigate a number of problems related to 2-level polytopes, in particular from the point of view of the combinatorial structure and the extension complexity. 2-level polytopes were introduced as a generalization of stable set polytopes ...

EPFL2018

A Non-Stationary Subdivision Scheme for the Construction of Deformable Models with Sphere-Like Topology

Michaël Unser, Daniel Andreas Schmitter, Anaïs Laure Marie-Thérèse Badoual

We present an affine-invariant non-stationary subdivision scheme for the recursive refinement of any triangular mesh that is regular or has extraordinary vertices of valence 4. In particular, when applied to an arbitrary convex octahedron, it produces a $ ...

2017

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

Extended Reverse Convex Programming: An Active-Set Approach to Global Optimization

Gene Bunin

Reverse convex programming (RCP) represents an important class of global optimization problems consisting of concave cost and inequality constraint functions. While useful in many practical scenarios due to the frequent appearance of concave models, a more ...

Springer Verlag2016

Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes

Friedrich Eisenbrand

This paper features two main contributions. On the one hand, it gives an impressive survey on the progress on the diameter problem, including the breakthrough of the author with his disproof of the Hirsch conjecture among many other recent results. On the ...

Springer2013

Least-restrictive robust periodic model predictive control applied to room temperature regulation

Colin Neil Jones

State-feedback model predictive control (MPC) of constrained discrete-time periodic affine systems is considered. The periodic systems’ states and inputs are subject to periodically time-dependent, hard, polyhedral constraints. Disturbances are additive, b ...

Elsevier2013

Extended Formulations, Nonnegative Factorizations, and Randomized Communication Protocols

Yuri Faenza, Hans Raj Tiwary

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