DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2023.23

Clustering in Polygonal Domains

Authors: Mark de Berg, Leyla Biabani, Morteza Monemizadeh, and Leonidas Theocharous

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract

We study various clustering problems for a set D of n points in a polygonal domain P under the geodesic distance. We start by studying the discrete k-median problem for D in P. We develop an exact algorithm which runs in time poly(n,m) + n^O(√k), where m is the complexity of the domain. Subsequently, we show that our approach can also be applied to solve the k-center problem with z outliers in the same running time. Next, we turn our attention to approximation algorithms. In particular, we study the k-center problem in a simple polygon and show how to obtain a (1+ε)-approximation algorithm which runs in time 2^{O((k log(k))/ε)} (n log(m) + m). To obtain this, we demonstrate that a previous approach by Bădoiu et al. [Bâdoiu et al., 2002; Bâdoiu and Clarkson, 2003] that works in ℝ^d, carries over to the setting of simple polygons. Finally, we study the 1-center problem in a simple polygon in the presence of z outliers. We show that a coreset C of size O(z) exists, such that the 1-center of C is a 3-approximation of the 1-center of D, when z outliers are allowed. This result is actually more general and carries over to any metric space, which to the best of our knowledge was not known so far. By extending this approach, we show that for the 1-center problem under the Euclidean metric in ℝ², there exists an ε-coreset of size O(z/ε).

Cite as

Mark de Berg, Leyla Biabani, Morteza Monemizadeh, and Leonidas Theocharous. Clustering in Polygonal Domains. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ISAAC.2023.23,
  author =	{de Berg, Mark and Biabani, Leyla and Monemizadeh, Morteza and Theocharous, Leonidas},
  title =	{{Clustering in Polygonal Domains}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.23},
  URN =		{urn:nbn:de:0030-drops-193252},
  doi =		{10.4230/LIPIcs.ISAAC.2023.23},
  annote =	{Keywords: clustering, geodesic distance, coreset, outliers}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2021.73

Maximum-Weight Matching in Sliding Windows and Beyond

Authors: Leyla Biabani, Mark de Berg, and Morteza Monemizadeh

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract

We study the maximum-weight matching problem in the sliding-window model. In this model, we are given an adversarially ordered stream of edges of an underlying edge-weighted graph G(V,E), and a parameter L specifying the window size, and we want to maintain an approximation of the maximum-weight matching of the current graph G(t); here G(t) is defined as the subgraph of G consisting of the edges that arrived during the time interval [max(t-L,1),t], where t is the current time. The goal is to do this with Õ(n) space, where n is the number of vertices of G. We present a deterministic (3.5+ε)-approximation algorithm for this problem, thus significantly improving the (6+ε)-approximation algorithm due to Crouch and Stubbs [Michael S. Crouch and Daniel M. Stubbs, 2014]. We also present a generic machinery for approximating subadditve functions in the sliding-window model. A function f is called subadditive if for every disjoint substreams A, B of a stream S it holds that f(AB) ⩽ f(A) + f(B), where AB denotes the concatenation of A and B. We show that given an α-approximation algorithm for a subadditive function f in the insertion-only model we can maintain a (2α+ε)-approximation of f in the sliding-window model. This improves upon recent result Krauthgamer and Reitblat [Robert Krauthgamer and David Reitblat, 2019], who obtained a (2α²+ε)-approximation.

Cite as

Leyla Biabani, Mark de Berg, and Morteza Monemizadeh. Maximum-Weight Matching in Sliding Windows and Beyond. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 73:1-73:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{biabani_et_al:LIPIcs.ISAAC.2021.73,
  author =	{Biabani, Leyla and de Berg, Mark and Monemizadeh, Morteza},
  title =	{{Maximum-Weight Matching in Sliding Windows and Beyond}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{73:1--73:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.73},
  URN =		{urn:nbn:de:0030-drops-155061},
  doi =		{10.4230/LIPIcs.ISAAC.2021.73},
  annote =	{Keywords: maximum-weight matching, sliding-window model, approximation algorithm, and subadditve functions}
}

Search Results

Documents authored by Biabani, Leyla

Clustering in Polygonal Domains

Abstract

Cite as

Maximum-Weight Matching in Sliding Windows and Beyond

Abstract

Cite as

Thanks for your feedback!

Could not send message