A. de Mesmay

activity

20112023

most citedOn the Complexity of Immersed Normal Surfaces

6 citations · 10 across the 12 of their papers we have counts for

collaborators

Showing cs.DSShow all

3 papers · 1 filter

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…

cs.DS2021

Voting algorithms for unique games on complete graphs

Antoine Méot, Arnaud de Mesmay, Moritz Mühlenthaler +1

An approximation algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying a $(1 - f (ε))$ -fraction of the constraints on any $(1 - ε)$ -s…

cs.DS2016

A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs with a Fixed Number of Terminals

Vincent Cohen-Addad, Éric Colin de Verdière, Arnaud de Mesmay

For an undirected edge-weighted graph $G$ and a set $R$ of pairs of vertices called pairs of terminals, a multicut is a set of edges such that removing these edges from $G$ disconn…