Publication

The Holt-Klee condition for oriented matroids

Publications associées (28)

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Knapsack problems give a simple framework for decision making. A classical example is the min-knapsack problem (MinKnap): choose a subset of items with minimum total cost, whose total profit is above a given threshold. While this model successfully general ...

EPFL2019

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

Edge Ordered Turan Problems

Doemoetoer Palvoelgyi, Gábor Tardos, Abhishek Methuku

We introduce the Turan problem for edge ordered graphs. We call a simple graph edge ordered, if its edges are linearly ordered. An isomorphism between edge ordered graphs must respect the edge order. A subgraph of an edge ordered graph is itself an edge or ...

COMENIUS UNIV2019

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

Matching fields and lattice points of simplices

Georg Peter Loho

We show that the Chow covectors of a linkage matching field define a bijection of lattice points and we demonstrate how one can recover the linkage matching field from this bijection. This resolves two open questions from Sturmfels & Zelevinsky (1993) on l ...

2020

Anomalous Vp/Vs ratios at seismic frequencies might evidence highly damaged rocks in subduction zones

Marie Estelle Solange Violay, Lucas Xan Pimienta

Unusually high compressional (P) to shear (S) wave velocity ratios (V-p/V-s) were measured at different subduction zones and interpreted as fluid-pressurized regions. Because no laboratory data reported such high values in isotropic rocks, mineralogical or ...

2018

Execution Trace Graph of Dataflow Process Networks

Marco Mattavelli, Simone Casale Brunet

The paper introduces and specifies a formalism that provides complete representations of dataflow process network (DPN) program executions, by means of directed acyclic graphs. Such graphs, also known as execution trace graphs (ETG), are composed of nodes ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2018

Extensive amenability and an application to interval exchanges

Nicolas Monod, Nicolas Matte Bon

Extensive amenability is a property of group actions which has recently been used as a tool to prove amenability of groups. We study this property and prove that it is preserved under a very general construction of semidirect products. As an application, w ...

2018