Arnaud de Mesmay

activity

20142023

collaborators

4 papers

cs.DS2023

A PTAS for $ℓ_{0}$ -Low Rank Approximation: Solving Dense CSPs over Reals

Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal +4

We consider the Low Rank Approximation problem, where the input consists of a matrix $A \in R^{n_{R} \times n_{C}}$ and an integer $k$ , and the goal is to find a matrix $B$ of…

math.GT2023

Universal families of arcs and curves on surfaces

Niloufar Fuladi, Arnaud de Mesmay, Hugo Parlier

The main goal of this paper is to investigate the minimal size of families of curves on surfaces with the following property: a family of simple closed curves $Γ$ on a surface real…

cs.DS2022

Fitting Metrics and Ultrametrics with Minimum Disagreements

Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee +1

Given $x \in (R_{\geq 0})^{(2 [ n ])}$ recording pairwise distances, the METRIC VIOLATION DISTANCE (MVD) problem asks to compute the $ℓ_{0}$ distance between $x$ and…

math.CO2014

Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces

Éric Colin de Verdière, Alfredo Hubard, Arnaud de Mesmay

How much cutting is needed to simplify the topology of a surface? We provide bounds for several instances of this question, for the minimum length of topologically non-trivial clos…

A PTAS for ℓ0​-Low Rank Approximation: Solving Dense CSPs over Reals

Universal families of arcs and curves on surfaces

Fitting Metrics and Ultrametrics with Minimum Disagreements

Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces

A PTAS for $ℓ_{0}$ -Low Rank Approximation: Solving Dense CSPs over Reals