Publication

Weakly regular subdivisions

Publications associées (29)

Capture zone models of a multi-well system in aquifers bounded with regular and irregular inflow boundaries

Being bounded by hydrological (inflow and barrier) boundaries, natural aquifers have regular/irregular shapes. Here, we consider aquifers bounded by segmental inflow (variable head) boundaries in which water is extracted/injected by a multi-well system. St ...

2020

Tropical 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 ...

2019

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

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

Design and Performance Evaluation of an Infotaxis-Based Three-Dimensional Algorithm for Odor Source Localization

Alcherio Martinoli, Ali Marjovi, Faezeh Rahbar, Julian Ruddick

In this paper we tackle the problem of finding the source of a gaseous leak with a robot in a three-dimensional (3-D) physical space. The proposed method extends the operational range of the probabilistic Infotaxis algorithm [1] into 3-D and makes multiple ...

IEEE2018

Non-Normal Very Ample Polytopes - Constructions and Examples

Michal Lason

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 Inc2017

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

The mixing time of the Dikin walk in a polytope-A simple proof

Nisheeth Vishnoi

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 Bv2016

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