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.APPROX/RANDOM.2023.25
URN: urn:nbn:de:0030-drops-188503
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18850/
Go to the corresponding LIPIcs Volume Portal

Mahabadi, Sepideh ; Narayanan, Shyam

Improved Diversity Maximization Algorithms for Matching and Pseudoforest

pdf-format:
LIPIcs-APPROX25.pdf (0.8 MB)

Abstract

In this work we consider the diversity maximization problem, where given a data set X of n elements, and a parameter k, the goal is to pick a subset of X of size k maximizing a certain diversity measure. Chandra and Halldórsson [Barun Chandra and Magnús M. Halldórsson, 2001] defined a variety of diversity measures based on pairwise distances between the points. A constant factor approximation algorithm was known for all those diversity measures except "remote-matching", where only an O(log k) approximation was known. In this work we present an O(1) approximation for this remaining notion. Further, we consider these notions from the perpective of composable coresets. Indyk et al. [Piotr Indyk et al., 2014] provided composable coresets with a constant factor approximation for all but "remote-pseudoforest" and "remote-matching", which again they only obtained a O(log k) approximation. Here we also close the gap up to constants and present a constant factor composable coreset algorithm for these two notions. For remote-matching, our coreset has size only O(k), and for remote-pseudoforest, our coreset has size O(k^{1+ε}) for any ε > 0, for an O(1/ε)-approximate coreset.

BibTeX - Entry

@InProceedings{mahabadi_et_al:LIPIcs.APPROX/RANDOM.2023.25,
  author =	{Mahabadi, Sepideh and Narayanan, Shyam},
  title =	{{Improved Diversity Maximization Algorithms for Matching and Pseudoforest}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{25:1--25:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18850},
  URN =		{urn:nbn:de:0030-drops-188503},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.25},
  annote =	{Keywords: diversity maximization, approximation algorithms, composable coresets}
}

Keywords: diversity maximization, approximation algorithms, composable coresets
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Issue Date: 2023
Date of publication: 04.09.2023

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