• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

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

Indexed by:

EI Scopus SCIE

Abstract:

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.

Keyword:

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

Author Community:

  • [ 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

Reprint Author's Address:

  • 徐大川

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

Show more details

Related Keywords:

Source :

OPTIMIZATION AND ENGINEERING

ISSN: 1389-4420

Year: 2020

Issue: 3

Volume: 21

Page: 709-722

2 . 1 0 0

JCR@2022

ESI Discipline: ENGINEERING;

ESI HC Threshold:115

Cited Count:

WoS CC Cited Count: 10

SCOPUS Cited Count: 13

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 9

Online/Total:1216/10606759
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.