A Simple Algorithm for r-gather-clusterings on the Line

• Item type: SIG Technical Reports(1)
• 公開日: 2017-01-10
• タイトル: A Simple Algorithm for r-gather-clusterings on the Line
• タイトル / 言語: en
• タイトル: A Simple Algorithm for r-gather-clusterings on the Line
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Gunma University
• 著者所属(英): en
• 著者所属(英): Gunma University
• 著者名: Shin-ichi, Nakano
• 著者名(英): Shin-ichi, Nakano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: In this paper we study a recently proposed two variants of the facility location problem, called the r-gather-clustering problem and the r-gathering problem. Given a set C of n points on the plane an r-gather-clustering is a partition of the points into clusters such that each cluster has at least r points. The r-gather-clustering problem finds the r-gather-clustering minimizing the maximum radius among the clusters, where the radius of a cluster is the minimum radius of the disk which can cover the points in the cluster. A polynomial time 2-approximation algorithm for the problem is known. When all C are on the line, an O (n log n) time algorithm, based on the matrix search method, to find an r-gather-clustering is known. In this paper we give an O (n log* n) time algorithm to solve the problem. We also give an algorithm to solve a similar problem, called the r-gathering problem.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper we study a recently proposed two variants of the facility location problem, called the r-gather-clustering problem and the r-gathering problem. Given a set C of n points on the plane an r-gather-clustering is a partition of the points into clusters such that each cluster has at least r points. The r-gather-clustering problem finds the r-gather-clustering minimizing the maximum radius among the clusters, where the radius of a cluster is the minimum radius of the disk which can cover the points in the cluster. A polynomial time 2-approximation algorithm for the problem is known. When all C are on the line, an O(n log n) time algorithm, based on the matrix search method, to find an r-gather-clustering is known. In this paper we give an O (n log* n) time algorithm to solve the problem. We also give an algorithm to solve a similar problem, called the r-gathering problem.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2017-AL-161, 号 9, p. 1-3, 発行日 2017-01-10
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会