Pauline Sarrabezolles

activity

20122016

collaborators

Showing math.OCShow all

2 papers · 1 filter

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…