Clustering through Continuous Facility Location Problems

详细信息    查看全文

• 作者：Luis A.A. Meira^a ; ^{meira@ft.unicamp.br} ; Flá ; vio K. Miyazawa^b ; ^{fkm@ic.unicamp.br} ; Lehilton L.C. Pedrosa^b ; ^{lehilton@ic.unicamp.br}
• 关键词：Continuous Facility Location Problem ; k-Clustering ; Approximate center sets ; Random sampling procedure ; Approximation algorithms
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：2 January 2017
• 年：2017
• 卷：657
• 期：part_PB
• 页码：137-145
• 全文大小：365 K
• 卷排序：657

文摘

We consider the Continuous Facility Location Problem (ConFLP). Given a finite set of clients C⊂RdC⊂Rd and a number f∈R+f∈R+, ConFLP consists in opening a set F′⊂RdF′⊂Rd of facilities, each at cost f, and connecting each client to an open facility. The objective is to minimize the costs of opening facilities and connecting clients. We reduce ConFLP to the standard Facility Location Problem (FLP), by using the so-called approximate center sets. This reduction preserves the approximation, except for an error ε  , and implies 1.488+ε1.488+ε and 2.04+ε2.04+ε-approximations when the connection cost is given by the Euclidean distance and the squared Euclidean distance, respectively. Moreover, we obtain approximate center sets for the case that the connection cost is the α  th power of the Euclidean distance, achieving approximations for the corresponding problems, for any α≥1α≥1. As a byproduct, we also obtain a polynomial-time approximation scheme for the k-median problem with this cost function, for any fixed k.