License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.13
URN: urn:nbn:de:0030-drops-180656
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18065/
Go to the corresponding LIPIcs Volume Portal


Azar, Yossi ; Vainstein, Danny

Multi Layer Peeling for Linear Arrangement and Hierarchical Clustering

pdf-format:
LIPIcs-ICALP-2023-13.pdf (0.8 MB)


Abstract

We present a new multi-layer peeling technique to cluster points in a metric space. A well-known non-parametric objective is to embed the metric space into a simpler structured metric space such as a line (i.e., Linear Arrangement) or a binary tree (i.e., Hierarchical Clustering). Points which are close in the metric space should be mapped to close points/leaves in the line/tree; similarly, points which are far in the metric space should be far in the line or on the tree. In particular we consider the Maximum Linear Arrangement problem [Refael Hassin and Shlomi Rubinstein, 2001] and the Maximum Hierarchical Clustering problem [Vincent Cohen-Addad et al., 2018] applied to metrics.
We design approximation schemes (1-ε approximation for any constant ε > 0) for these objectives. In particular this shows that by considering metrics one may significantly improve former approximations (0.5 for Max Linear Arrangement and 0.74 for Max Hierarchical Clustering). Our main technique, which is called multi-layer peeling, consists of recursively peeling off points which are far from the "core" of the metric space. The recursion ends once the core becomes a sufficiently densely weighted metric space (i.e. the average distance is at least a constant times the diameter) or once it becomes negligible with respect to its inner contribution to the objective. Interestingly, the algorithm in the Linear Arrangement case is much more involved than that in the Hierarchical Clustering case, and uses a significantly more delicate peeling.

BibTeX - Entry

@InProceedings{azar_et_al:LIPIcs.ICALP.2023.13,
  author =	{Azar, Yossi and Vainstein, Danny},
  title =	{{Multi Layer Peeling for Linear Arrangement and Hierarchical Clustering}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18065},
  URN =		{urn:nbn:de:0030-drops-180656},
  doi =		{10.4230/LIPIcs.ICALP.2023.13},
  annote =	{Keywords: Hierarchical clustering, Linear arrangements, Metric embeddings}
}

Keywords: Hierarchical clustering, Linear arrangements, Metric embeddings
Collection: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Issue Date: 2023
Date of publication: 05.07.2023


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI