Pauline Sarrabezolles

activity

20122016

collaborators

6 papers

cs.CG2016

The Rainbow at the End of the Line --- A PPAD Formulation of the Colorful Carathéodory Theorem with Applications

Frédéric Meunier, Wolfgang Mulzer, Pauline Sarrabezolles +1

Let $C_{1}, ..., C_{d + 1}$ be $d + 1$ point sets in $R^{d}$ , each containing the origin in its convex hull. A subset $C$ of $⋃_{i = 1}^{d + 1} C_{i}$ is called a colorful choice (o…

math.OC2015

The Unimodular Intersection Problem

Volker Kaibel, Shmuel Onn, Pauline Sarrabezolles

We show that finding minimally intersecting $n$ paths from $s$ to $t$ in a directed graph or $n$ perfect matchings in a bipartite graph can be done in polynomial time. This holds m…

math.OC2015

Huge Unimodular N-Fold Programs

Shmuel Onn, Pauline Sarrabezolles

Optimization over $l \times m \times n$ integer $3$ -way tables with given line-sums is NP-hard already for fixed $l = 3$ , but is polynomial time solvable with both $l, m$ fixed. In the…

cs.DM2014

Colorful linear programming, Nash equilibrium, and pivots

Frédéric Meunier, Pauline Sarrabezolles

The colorful Carathéodory theorem, proved by Bárány in 1982, states that given d+1 sets of points S_1,...,S_{d+1} in R^d, with each S_i containing 0 in its convex hull, there exist…

math.CO2014

The colourful simplicial depth conjecture

Pauline Sarrabezolles

Given $d + 1$ sets of points, or colours, $S_{1}, \dots, S_{d + 1}$ in $R^{d}$ , a colourful simplex is a set $T \subseteq ⋃_{i = 1}^{d + 1} S_{i}$ such that $∣ T \cap S_{i} ∣ \leq 1$ , for al…

math.CO2012

A combinatorial approach to colourful simplicial depth

Antoine Deza, Frédéric Meunier, Pauline Sarrabezolles

The colourful simplicial depth conjecture states that any point in the convex hull of each of d+1 sets, or colours, of d+1 points in general position in R^d is contained in at leas…