FIT2016 第15回情報科学技術フォーラム 開催日:2016年9月7日(水)~9日(金) 会場:富山大学キャンパス
l-diversity clustering on the line
Toshihiro Akagi・Shin-ichi Nakano(Gunma Univ.)
Given a set of n points having a color, a set of m colors, the distance d between each pair of points, and a number l, an l-diversity clustering is a partition of points into clusters such that each cluster has at least l points all of which have distinct colors.
We define the cost of an l-diversity clustering as the maximum diameter of clusters.
We designed an algorithm to find the l-diversity clustering having the minimum cost when all points are on the line. The running time is O(2m*(n/m+1)m).