Publication

Order Types of Convex Bodies

Publications associées (30)

Between the Pattern and the Type: A short parallel story

Historically speaking, the notion of the type was reintroduced to the larger architectural discourse as a direct consequence of the crisis of the Modern. The task of revisiting the forms of the past also dictated the return of architectural methods that ha ...

2023

Quadratic serendipity element shape functions on general planar polygons

Juan Cao, Xiaodong Wei

This paper proposes a method for the construction of quadratic serendipity element (QSE) shape functions on planar convex and concave polygons. Existing approaches for constructing QSE shape functions are linear combinations of the pair-wise products of ge ...

ELSEVIER SCIENCE SA2022

Streaming and Matching Problems with Submodular Functions

Paritosh Garg

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...

EPFL2022

Scaling Language Features for Program Verification

Georg Stefan Schmid

Formal verification of real-world software systems remains challenging for a number of reasons, including lack of automation, friction in specifying properties, and limited support for the diverse programming paradigms used in industry. In this thesis we m ...

EPFL2022

A Theory of Value for Service Ecosystems

Blagovesta Hristova Kostova

In this thesis, we present a theory of value for the design and analysis of service ecosystems. The theory is based on general systems thinking. The concept of a system is used for relating knowledge from different disciplines (such as software engineering ...

EPFL2022

Quantum yield and brightness

Jean-Claude Bünzli

Brightness has different meaning in different contexts and some of these are reviewed. The scientific definition of brightness does not represent our perception. The current definition is that from the IUPAC Gold Book and is mainly restricted to solutions. ...

2020

Integral Convexity And Parabolic Systems

Bernard Dacorogna

In this work we give optimal, i.e., necessary and sufficient, conditions for integrals of the calculus of variations to guarantee the existence of solutions-both weak and variational solutions-to the associated L-2-gradient flow. The initial values are mer ...

SIAM PUBLICATIONS2020

Entropic Matroids and Their Representation

Emmanuel Abbé

This paper investigates entropic matroids, that is, matroids whose rank function is given as the Shannon entropy of random variables. In particular, we consider p-entropic matroids, for which the random variables each have support of cardinality p. We draw ...

2019

Cross-sections of line configurations in R-3 and (d-2)-flat configurations in R-d

Andres Jacinto Ruiz Vargas

We consider sets L = {l(1),..., l(n)} of n labeled lines in general position in R-3, and study the order types of point sets {p(1),..., p(n)} that stem from the intersections of the lines in L with (directed) planes Pi, not parallel to any line of L, that ...

ELSEVIER SCIENCE BV2019

Nested Convex Bodies are Chaseable

Marek Elias

In the Convex Body Chasing problem, we are given an initial point v0. Rd and an online sequence of n convex bodies F1,..., Fn. When we receive Ft, we are required to move inside Ft. Our goal is to minimize the total distance traveled. This fundamental onli ...

SPRINGER2020

An Improved Analysis of Local Search for Max-Sum Diversification

Rico Zenklusen, Friedrich Eisenbrand, Alfonso Bolívar Cevallos Manzano

We present new techniques to analyze natural local search algorithms for several variants of the max-sum diversification problem which, in its most basic form, is as follows: given an n-point set X subset of R-d and an integer k, select k points in X so th ...

INFORMS2019

The covering radius and a discrete surface area for non-hollow simplices

Matthias Schymura

We explore upper bounds on the covering radius of non-hollow lattice polytopes. In particular, we conjecture a general upper bound of d/2 in dimension d, achieved by the "standard terminal simplices" and direct sums of them. We prove this conjecture up to ...

2022

Verified Functional Programming

Nicolas Charles Yves Voirol

In this thesis, we present Stainless, a verification system for an expressive subset of the Scala language. Our system is based on a dependently-typed language and an algorithmic type checking procedure which ensures total correctness. We rely on SMT solve ...

EPFL2019

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

Igor Malinovic

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

On the reverse isodiametric problem and Dvoretzky-Rogers-type volume bounds

Matthias Schymura

The isodiametric inequality states that the Euclidean ball maximizes the volume among all convex bodies of a given diameter. We are motivated by a conjecture of Makai Jr. on the reverse question: Every convex body has a linear image whose isodiametric quot ...

2018

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

Automated Eardrum Registration From Light-Field Data

Pascal Frossard, Ivana Tosic, Sofia Karygianni

The performance of automated classification algorithms for medical images needs to be very high and especially robust in order to be adopted into healthcare. Most of the time the main challenge is unregistered data, since it is usually captured: 1) from di ...

IEEE2018

Optimization of sample size and order size in an inventory model with quality inspection and return of defective items

Naoufel Cheikhrouhou, Rafael Batista

To ensure all products as perfect, inspection is essential, even though it is not possible to inspect all products after producing them like some special type products as plastic joint for the water pipe. In this direction, this paper develops an inventory ...

SPRINGER2018

On some algebraic and extremal problems in discrete geometry

Seyed Hossein Nassajianmojarrad

In the present thesis, we delve into different extremal and algebraic problems arising from combinatorial geometry. Specifically, we consider the following problems. For any integer

n\ge 3

, we define

e(n)

to be the minimum positive integer such that an ...

EPFL2017

Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration

Javad Ebrahimi Boroojeni, Damian Mateusz Straszak, Nisheeth Vishnoi

Several fundamental problems that arise in optimization and computer science can be cast as follows: Given vectors v(1), ..., v(m) is an element of R-d and a constraint family B subset of 2([m]), find a set S. B that maximizes the squared volume of the sim ...

Ieee2017