1 Search Results for "Mirsadeghi, Mir Omid Haji"

Document

DOI: 10.4230/LIPIcs.SWAT.2020.3

Preclustering Algorithms for Imprecise Points

Authors: Mohammad Ali Abam, Mark de Berg, Sina Farahzad, Mir Omid Haji Mirsadeghi, and Morteza Saghafian

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract

We study the problem of preclustering a set B of imprecise points in ℝ^d: we wish to cluster the regions specifying the potential locations of the points such that, no matter where the points are located within their regions, the resulting clustering approximates the optimal clustering for those locations. We consider k-center, k-median, and k-means clustering, and obtain the following results. Let B:={b₁,…,b_n} be a collection of disjoint balls in ℝ^d, where each ball b_i specifies the possible locations of an input point p_i. A partition 𝒞 of B into subsets is called an (f(k),α)-preclustering (with respect to the specific k-clustering variant under consideration) if (i) 𝒞 consists of f(k) preclusters, and (ii) for any realization P of the points p_i inside their respective balls, the cost of the clustering on P induced by 𝒞 is at most α times the cost of an optimal k-clustering on P. We call f(k) the size of the preclustering and we call α its approximation ratio. We prove that, even in ℝ^1, one may need at least 3k-3 preclusters to obtain a bounded approximation ratio - this holds for the k-center, the k-median, and the k-means problem - and we present a (3k,1) preclustering for the k-center problem in ℝ^1. We also present various preclusterings for balls in ℝ^d with d⩾2, including a (3k,α)-preclustering with α≈13.9 for the k-center and the k-median problem, and α≈254.7 for the k-means problem.

Cite as

Mohammad Ali Abam, Mark de Berg, Sina Farahzad, Mir Omid Haji Mirsadeghi, and Morteza Saghafian. Preclustering Algorithms for Imprecise Points. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{abam_et_al:LIPIcs.SWAT.2020.3,
  author =	{Abam, Mohammad Ali and de Berg, Mark and Farahzad, Sina and Mirsadeghi, Mir Omid Haji and Saghafian, Morteza},
  title =	{{Preclustering Algorithms for Imprecise Points}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{3:1--3:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.3},
  URN =		{urn:nbn:de:0030-drops-122503},
  doi =		{10.4230/LIPIcs.SWAT.2020.3},
  annote =	{Keywords: Geometric clustering, k-center, k-means, k-median, imprecise points, approximation algorithms}
}

Refine by Author
1 Abam, Mohammad Ali
1 Farahzad, Sina
1 Mirsadeghi, Mir Omid Haji
1 Saghafian, Morteza
1 de Berg, Mark

Refine by Classification
1 Theory of computation → Design and analysis of algorithms

Refine by Keyword
1 Geometric clustering
1 approximation algorithms
1 imprecise points
1 k-center
1 k-means
Show More...

Refine by Type
1 document

Refine by Publication Year
1 2020

1 Search Results for "Mirsadeghi, Mir Omid Haji"

Preclustering Algorithms for Imprecise Points

Abstract

Cite as

Thanks for your feedback!

Could not send message