Publication
Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
Publications associées (33)
Safe Motion Planning against Multimodal Distributions Based on a Scenario Approach
We present the design of a motion planning algorithm that ensures safety for an autonomous vehicle. In particular, we consider a multimodal distribution over uncertainties; for example, the uncertain predictions of future trajectories of surrounding vehicl ...
2022Reduced representations of complexes, signals, and multifiltrations
The field of computational topology has developed many powerful tools to describe the shape of data, offering an alternative point of view from classical statistics. This results in a variety of complex structures that are not always directly amenable for ...
EPFL2022Tropical Ehrhart Theory and Tropical Volume
Matthias Schymura, Georg Peter Loho
We introduce a novel intrinsic volume concept in tropical geometry. This is achieved by developing the foundations of a tropical analog of lattice point counting in polytopes. We exhibit the basic properties and compare it to existing measures. Our exposit ...
2019Extended 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 AG2019On 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 PUBLICATIONS2018On some problems related to 2-level polytopes
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 ...
EPFL2018Non-Normal Very Ample Polytopes - Constructions and Examples
We answer several questions posed by Beck, Cox, Delgado, Gubeladze, Haase, Hibi, Higashitani, and Maclagan in [Cox et al. 14, Question 3.5 (1),(2), Question 3.6], [Beck et al. 15, Conjecture 3.5(a),(b)], and [Hasse et al. 07, Open question 3 (a),(b) p. 231 ...
Taylor & Francis Inc2017Extension 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. ...
Springer2017The mixing time of the Dikin walk in a polytope-A simple proof
We study the mixing time of the Dikin walk in a polytope a random walk based on the log-barrier from the interior point method literature. This walk, and a close variant, were studied by Narayanan (2016) and Kannan-Narayanan (2012). Bounds on its mixing ti ...
Elsevier Science Bv2016On 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