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

Author:

Wu, Chenchen (Wu, Chenchen.) | Moehring, Rolf H. (Moehring, Rolf H..) | Wang, Yishui (Wang, Yishui.) | Xu, Dachuan (Xu, Dachuan.) (Scholars:徐大川) | Zhang, Dongmei (Zhang, Dongmei.)

Indexed by:

CPCI-S EI Scopus

Abstract:

In this paper, we explore two robust models for the k-median and k-means problems: the outlier-version (k-MedO/k-MeaO) and the penalty-version (k-MedP/k-MeaP), enabling the marking and elimination of certain points as outliers. In k-MedO/k-MeaO, the count of outliers is restricted by a specified integer, while in k-MedP/k-MeaP, there's no explicit limit on outlier quantity, yet each outlier incurs a penalty cost. We introduce a novel approach to evaluate the approximation ratio of local search algorithms for these problems. This involves an adapted clustering method that captures pertinent information about outliers within both local and global optimal solutions. For k-MeaP, we enhance the best-known approximation ratio derived from local search, elevating it from 25 + epsilon to 9 + epsilon. The best-known approximation ratio for k-MedP is also obtained. Regarding k-MedO/k-MeaO, only two bi-criteria approximation algorithms based on local search exist. One violates the outlier constraint (limiting outlier count), while the other breaches the cardinality constraint (restricting the number of clusters). We focus on the former algorithm, enhancing its approximation ratios from 17+epsilon to 3+epsilon for k-MedO and from 274 + epsilon to 9 + epsilon for k-MeaO.

Keyword:

Clustering Problems Robust Approximation algorithms

Author Community:

  • [ 1 ] [Wu, Chenchen]Tianjin Univ Technol, Coll Sci, Inst Operat Res & Syst Engn, Tianjin 300384, Peoples R China
  • [ 2 ] [Moehring, Rolf H.]Hefei Univ, Inst Appl Optimizat, Dept Comp Sci & Technol, Hefei, Peoples R China
  • [ 3 ] [Moehring, Rolf H.]Tech Univ Berlin, Inst Math, Combinatorial Optimizat & Graph Algorithms COGA G, Berlin, Germany
  • [ 4 ] [Wang, Yishui]Univ Sci & Technol Beijing, Sch Math & Phys, Beijing, Peoples R China
  • [ 5 ] [Xu, Dachuan]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China
  • [ 6 ] [Zhang, Dongmei]Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China

Reprint Author's Address:

  • [Xu, Dachuan]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China;;

Show more details

Related Keywords:

Source :

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2024

ISSN: 0302-9743

Year: 2024

Volume: 14637

Page: 197-208

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Affiliated Colleges:

Online/Total:614/5336428
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.