标题:Local search approximation algorithms for the sum of squares facility location problems
作者:Zhang, Dongmei; Xu, Dachuan; Wang, Yishui; Zhang, Peng; Zhang, Zhenning
通讯作者:Xu, DC;Xu, Dachuan
作者机构:[Zhang, Dongmei] Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Shandong, Peoples R China.; [Xu, Dachuan] Beijing Univ Technol, Beijin 更多
会议名称:Global Optimization Conference (GOC)
会议日期:MAR 30-APR 01, 2017
来源:JOURNAL OF GLOBAL OPTIMIZATION
出版年:2019
卷:74
期:4
页码:909-932
DOI:10.1007/s10898-018-00733-2
关键词:Approximation algorithm; K-means; Facility location; Local search
摘要:In this paper, we study the sum of squares facility location problem (SOS-FLP) which is an important variant of k-means clustering. In the SOS-FLP, we are given a client set C subset of R-p and a uniform center opening cost f > 0. The goal is to open a finite center subset F subset of R-p and to connect each client to the closest open center such that the total cost including center opening cost and the sum of squares of distances is minimized. The SOS-FLP is introduced firstly by Bandyapadhyay and Varadarajan (in: Proceedings of SoCG 2016, Article No. 14, pp 14: 1-14: 15, 2016) which present a PTAS for the fixed dimension case. Using local search and scaling techniques, we offer the first constant approximation algorithm for the SOS-FLP with general dimension. We further consider the discrete version of SOS-FLP, in which we are given a finite candidate center set with nonuniform opening cost comparing with the aforementioned (continue) SOS-FLP. By exploring the structures of local and optimal solutions, we claim that the approximation ratios are 7.7721 + is an element of and 9 + is an element of for the continue and discrete SOS-FLP respectively.
收录类别:CPCI-S;EI;SCOPUS;SCIE
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-85059647490&doi=10.1007%2fs10898-018-00733-2&partnerID=40&md5=ccaa6c9350da178f9d1dcd89620a6f50
TOP