• 综合
  • 标题
  • 关键词
  • 摘要
  • 学者
  • 期刊-刊名
  • 期刊-ISSN
  • 会议名称
搜索

作者:

Xu, Yicheng (Xu, Yicheng.) | Moehring, Rolf H. (Moehring, Rolf H..) | Xu, Dachuan (Xu, Dachuan.) (学者:徐大川) | Zhang, Yong (Zhang, Yong.) (学者:张勇) | Zou, Yifei (Zou, Yifei.)

收录:

EI Scopus SCIE

摘要:

Hard-capacitated k-means (HCKM) is one of the fundamental problems remaining open in combinatorial optimization and engineering. In HCKM, one is required to partition a given n-point set into k disjoint clusters with known capacity so as to minimize the sum of within-cluster variances. It is known to be at least APX-hard, and most of the work on it has been done from a meta heuristic or bi-criteria approximation perspective. To the best our knowledge, no constant approximation algorithm or existence proof of such an algorithm is known. As our main contribution, we propose an FPT(k) approximation algorithm with constant performance guarantee for HCKM in this paper.

关键词:

k-means clustering Capacity constraints Approximation algorithm Fixed-parameter tractable

作者机构:

  • [ 1 ] [Xu, Yicheng]Chinese Acad Sci, Shenzhen Inst Adv Technol, Shenzhen 518055, Peoples R China
  • [ 2 ] [Zhang, Yong]Chinese Acad Sci, Shenzhen Inst Adv Technol, Shenzhen 518055, Peoples R China
  • [ 3 ] [Moehring, Rolf H.]Hefei Univ, Sch Artificial Intelligence & Big Data, Inst Appl Optimizat, Hefei 230601, Peoples R China
  • [ 4 ] [Moehring, Rolf H.]TU Berlin, Inst Math, D-10623 Berlin, Germany
  • [ 5 ] [Xu, Dachuan]Beijing Univ Technol, Dept Operat Res & Sci Comp, Beijing 100124, Peoples R China
  • [ 6 ] [Zou, Yifei]Univ Hong Kong, Dept Comp Sci, Pokfulam Rd, Hong Kong, Peoples R China

通讯作者信息:

  • 徐大川

    [Xu, Dachuan]Beijing Univ Technol, Dept Operat Res & Sci Comp, Beijing 100124, Peoples R China

查看成果更多字段

相关关键词:

来源 :

OPTIMIZATION AND ENGINEERING

ISSN: 1389-4420

年份: 2020

期: 3

卷: 21

页码: 709-722

2 . 1 0 0

JCR@2022

ESI学科: ENGINEERING;

ESI高被引阀值:115

被引次数:

WoS核心集被引频次: 10

SCOPUS被引频次: 13

ESI高被引论文在榜: 0 展开所有

万方被引频次:

中文被引频次:

近30日浏览量: 0

归属院系:

在线人数/总访问数:648/3905021
地址:北京工业大学图书馆(北京市朝阳区平乐园100号 邮编:100124) 联系我们:010-67392185
版权所有:北京工业大学图书馆 站点建设与维护:北京爱琴海乐之技术有限公司