1 Search Results for "Hassan, Md Yeakub"

Document

DOI: 10.4230/LIPIcs.SWAT.2020.22

Clustering Moving Entities in Euclidean Space

Authors: Stephane Durocher and Md Yeakub Hassan

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

Abstract

Clustering is a fundamental problem of spatio-temporal data analysis. Given a set 𝒳 of n moving entities, each of which corresponds to a sequence of τ time-stamped points in ℝ^d, a k-clustering of 𝒳 is a partition of 𝒳 into k disjoint subsets that optimizes a given objective function. In this paper, we consider two clustering problems, k-Center and k-MM, where the goal is to minimize the maximum value of the objective function over the duration of motion for the worst-case input 𝒳. We show that both problems are NP-hard when k is an arbitrary input parameter, even when the motion is restricted to ℝ. We provide an exact algorithm for the 2-MM clustering problem in ℝ^d that runs in O(τ d n²) time. The running time can be improved to O(τ n log{n}) when the motion is restricted to ℝ. We show that the 2-Center clustering problem is NP-hard in ℝ². Our 2-MM clustering algorithm provides a 1.15-approximate solution to the 2-Center clustering problem in ℝ². Moreover, finding a (1.15-ε)-approximate solution remains NP-hard for any ε >0. For both the k-MM and k-Center clustering problems in ℝ^d, we provide a 2-approximation algorithm that runs in O(τ d n k) time.

Cite as

Stephane Durocher and Md Yeakub Hassan. Clustering Moving Entities in Euclidean Space. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{durocher_et_al:LIPIcs.SWAT.2020.22,
  author =	{Durocher, Stephane and Hassan, Md Yeakub},
  title =	{{Clustering Moving Entities in Euclidean Space}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{22:1--22:14},
  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.22},
  URN =		{urn:nbn:de:0030-drops-122698},
  doi =		{10.4230/LIPIcs.SWAT.2020.22},
  annote =	{Keywords: trajectories, clustering, moving entities, k-CENTER, algorithms}
}

Refine by Author
1 Durocher, Stephane
1 Hassan, Md Yeakub

Refine by Classification
1 Theory of computation → Facility location and clustering

Refine by Keyword
1 algorithms
1 clustering
1 k-CENTER
1 moving entities
1 trajectories

Refine by Type
1 document

Refine by Publication Year
1 2020

1 Search Results for "Hassan, Md Yeakub"

Clustering Moving Entities in Euclidean Space

Abstract

Cite as

Thanks for your feedback!

Could not send message