The methods for approximation of principal points for binary distributions on the basis of submodularity

Haruka Yamashita; Hideo Suzuki

doi:10.1080/03610926.2013.781645

The methods for approximation of principal points for binary distributions on the basis of submodularity

Haruka Yamashita^*, Hideo Suzuki

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	2291-2309
Number of pages	19
Journal	Communications in Statistics - Theory and Methods
Volume	44
Issue number	11
DOIs	https://doi.org/10.1080/03610926.2013.781645
Publication status	Published - 2015 Jun 3

Keywords

Clustering
Data analysis
Multivariate binary distribution
Uncapacitated location problem

ASJC Scopus subject areas

Statistics and Probability

Access to Document

10.1080/03610926.2013.781645

Cite this

@article{70e7824eaea4432fa47dec642cbc55f3,

title = "The methods for approximation of principal points for binary distributions on the basis of submodularity",

abstract = "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.",

keywords = "Clustering, Data analysis, Multivariate binary distribution, Uncapacitated location problem",

author = "Haruka Yamashita and Hideo Suzuki",

year = "2015",

month = jun,

day = "3",

doi = "10.1080/03610926.2013.781645",

language = "English",

volume = "44",

pages = "2291--2309",

journal = "Communications in Statistics - Theory and Methods",

issn = "0361-0926",

publisher = "Taylor and Francis Ltd.",

number = "11",

}

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 -

The methods for approximation of principal points for binary distributions on the basis of submodularity

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this