Arnaud de Mesmay

activity

20142023

collaborators

Showing cs.DSShow all

2 papers · 1 filter

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…

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…

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

Fitting Metrics and Ultrametrics with Minimum Disagreements

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