TY - JOUR
T1 - The methods for approximation of principal points for binary distributions on the basis of submodularity
AU - Yamashita, Haruka
AU - Suzuki, Hideo
PY - 2015/6/3
Y1 - 2015/6/3
N2 - Principal points for binary distributions are able to be defined based on Flurys principal points (1990). However, finding principal points for binary distributions is hard in a straightforward manner. In this article, a method for approximating principal points for binary distributions is proposed by formulating it as an uncapacitated location problem. Moreover, it is shown that the problem of finding principal points can be solved with the aid of submodular functions. It leads to a solution whose value is at least (1 - 1/e) times the optimal value.
AB - Principal points for binary distributions are able to be defined based on Flurys principal points (1990). However, finding principal points for binary distributions is hard in a straightforward manner. In this article, a method for approximating principal points for binary distributions is proposed by formulating it as an uncapacitated location problem. Moreover, it is shown that the problem of finding principal points can be solved with the aid of submodular functions. It leads to a solution whose value is at least (1 - 1/e) times the optimal value.
KW - Clustering
KW - Data analysis
KW - Multivariate binary distribution
KW - Uncapacitated location problem
UR - http://www.scopus.com/inward/record.url?scp=84933074037&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84933074037&partnerID=8YFLogxK
U2 - 10.1080/03610926.2013.781645
DO - 10.1080/03610926.2013.781645
M3 - Article
AN - SCOPUS:84933074037
SN - 0361-0926
VL - 44
SP - 2291
EP - 2309
JO - Communications in Statistics - Theory and Methods
JF - Communications in Statistics - Theory and Methods
IS - 11
ER -