Arrow Research search

Author name cluster

Arnaud de Mesmay

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers
2 author rows

Possible papers

10

TCS Journal 2023 Journal Article

Distributed coloring and the local structure of unit-disk graphs

  • Louis Esperet
  • Sébastien Julliot
  • Arnaud de Mesmay

Coloring unit-disk graphs efficiently is an important problem in the global and distributed setting, with applications in radio channel assignment problems when the communication relies on omni-directional antennas of the same power. In this context it is important to bound not only the complexity of the coloring algorithms, but also the number of colors used. In this paper, we consider two natural distributed settings. In the location-aware setting (when nodes know their coordinates in the plane), we give a constant time distributed algorithm coloring any unit-disk graph G with at most 4 ω ( G ) colors, where ω ( G ) is the clique number of G. This improves upon a classical 3-approximation algorithm for this problem, for all unit-disk graphs whose chromatic number significantly exceeds their clique number. When nodes do not know their coordinates in the plane, we give a distributed algorithm in the LOCAL model that colors every unit-disk graph G with at most 5. 68 ω ( G ) + 1 colors in O ( log ⁎ ⁡ n ) rounds. This algorithm is based on a study of the local structure of unit-disk graphs, which is of independent interest. We conjecture that every unit-disk graph G has average degree at most 4 ω ( G ), which would imply the existence of a O ( log ⁡ n ) round algorithm coloring any unit-disk graph G with (approximately) 4 ω ( G ) colors in the LOCAL model. We provide partial results towards this conjecture using Fourier-analytical tools.

Details DOI

FOCS Conference 2022 Conference Paper

Fitting Metrics and Ultrametrics with Minimum Disagreements

  • Vincent Cohen-Addad
  • Chenglin Fan
  • Euiwoong Lee
  • Arnaud de Mesmay

Given $x\in(\mathbb{R}_{\geqslant 0})(_{2}^{[n]})$ recording pairwise distances, the Metric Violation Distance problem asks to compute the $\ell_{0}$ distance between x and the metric cone; i. e. , modify the minimum number of entries of x to make it a metric. Due to its large number of applications in various data analysis and optimization tasks, this problem has been actively studied recently. We present an $O(\log n)$-approximation algorithm for METRIC VIOLATION Distance, exponentially improving the previous best approximation ratio of $O(OPT^{1/3})$ of Fan, Raichel, and Van Buskirk [SODA, 2018]. Furthermore, a major strength of our algorithm is its simplicity and running time. We also study the related problem of Ultrametric Violation Distance, where the goal is to compute the $\ell_{0}$ distance to the cone of ultrametrics, and achieve a constant factor approximation algorithm. The ULTRAMETRIC VIOLATION DISTANCE problem can be regarded as an extension of the problem of fitting ultrametrics studied by Ailon and Charikar [SIAM J. Computing, 2011] and by Cohen-Addad, Das, Kipouridis, Parotsidis, and Thorup [FOCS, 2021] from $\ell_{1}$ norm to $\ell_{0}$ norm. We show that this problem can be favorably interpreted as an instance of CORRELATION CLUSTERING with an additional hierarchical structure, which we solve using a new $O(1)$-approximation algorithm for correlation clustering that has the structural property that it outputs a refinement of the optimum clusters. An algorithm satisfying such a property can be considered of independent interest. We also provide an $O(\log n\log\log n)$ approximation algorithm for weighted instances. Finally, we investigate the complementary version of these problems where one aims at choosing a maximum number of entries of x forming an (ultra-)metric. In stark contrast with the minimization versions, we prove that these maximization versions are hard to approximate within any constant factor assuming the Unique Games Conjecture.

Details

SODA Conference 2018 Conference Paper

Embeddability in ℝ 3 is NP-hard

  • Arnaud de Mesmay
  • Yo'av Rieck
  • Eric Sedgwick
  • Martin Tancer

We prove that the problem of deciding whether a 2- or 3-dimensional simplicial complex embeds into ℝ 3 is NP -hard. This stands in contrast with the lower dimensional cases which can be solved in linear time, and a variety of computational problems in ℝ 3 like unknot or 3-sphere recognition which are in NP ∩ co- NP (assuming the generalized Riemann hypothesis). Our reduction encodes a satisfiability instance into the embeddability problem of a 3-manifold with boundary tori, and relies extensively on techniques from low-dimensional topology, most importantly Dehn fillings on link complements.

Details

SODA Conference 2018 Conference Paper

On the complexity of optimal homotopies

  • Erin W. Chambers
  • Arnaud de Mesmay
  • Tim Ophelders

In this article, we provide new structural results and algorithms for the H omotopy H eight problem. In broad terms, this problem quantifies how much a curve on a surface needs to be stretched to sweep continuously between two positions. More precisely, given two homotopic curves γ 1 and γ 2 on a combinatorial (say, triangulated) surface, we investigate the problem of computing a homotopy between γ 1 and γ 2 where the length of the longest intermediate curve is minimized. Such optimal homotopies are relevant for a wide range of purposes, from very theoretical questions in quantitative homotopy theory to more practical applications such as similarity measures on meshes and graph searching problems. We prove that H omotopy H eight is in the complexity class NP, and the corresponding exponential algorithm is the best one known for this problem. This result builds on a structural theorem on monotonicity of optimal homotopies, which is proved in a companion paper. Then we show that this problem encompasses the H omotopic F réchet D istance problem which we therefore also establish to be in NP, answering a question which has previously been considered in several different settings. We also provide an O (log n )-approximation algorithm for H omotopy H eight on surfaces by adapting an earlier algorithm of Har-Peled, Nayyeri, Salvatipour and Sidiropoulos in the planar setting.

Details

SODA Conference 2018 Conference Paper

The Bane of Low-Dimensionality Clustering

  • Vincent Cohen-Addad
  • Arnaud de Mesmay
  • Eva Rotenberg
  • Alan Roytman

In this paper, we give a conditional lower bound of n Ω( k ) on running time for the classic k -median and k -means clustering objectives (where n is the size of the input), even in low-dimensional Euclidean space of dimension four, assuming the Exponential Time Hypothesis (ETH). We also consider k -median (and k -means) with penalties where each point need not be assigned to a center, in which case it must pay a penalty, and extend our lower bound to at least three-dimensional Euclidean space. This stands in stark contrast to many other geometric problems such as the traveling salesman problem, or computing an independent set of unit spheres. While these problems benefit from the so-called (limited) blessing of dimensionality, as they can be solved in time n O ( k 1-1/ d ) or 2 n 1-1/ d in d dimensions, our work shows that widely-used clustering objectives have a lower bound of n Ω( k ), even in dimension four. We complete the picture by considering the two-dimensional case: we show that there is no algorithm that solves the penalized version in time less than, and provide a matching upper bound of. The main tool we use to establish these lower bounds is the placement of points on the moment curve, which takes its inspiration from constructions of point sets yielding Delaunay complexes of high complexity.

Details

SODA Conference 2018 Conference Paper

Tightening Curves on Surfaces via Local Moves

  • Hsien-Chih Chang
  • Jeff Erickson 0001
  • David Letscher
  • Arnaud de Mesmay
  • Saul Schleimer
  • Eric Sedgwick
  • Dylan Thurston
  • Stephan Tillmann

We prove new upper and lower bounds on the number of homotopy moves required to tighten a closed curve on a compact orientable surface (with or without boundary) as much as possible. First, we prove that Ω( n 2 ) moves are required in the worst case to tighten a contractible closed curve on a surface with non-positive Euler characteristic, where n is the number of self-intersection points. Results of Hass and Scott imply a matching O ( n 2 ) upper bound for contractible curves on orientable surfaces. Second, we prove that any closed curve on any orientable surface can be tightened as much as possible using at most O ( n 4 ) homotopy moves. Except for a few special cases, only naïve exponential upper bounds were previously known for this problem.

Details