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

Author:

Ji, Sai (Ji, Sai.) | Cheng, Yukun (Cheng, Yukun.) | Tan, Jingjing (Tan, Jingjing.) | Zhao, Zhongrui (Zhao, Zhongrui.)

Indexed by:

CPCI-S EI Scopus

Abstract:

Correlation clustering problem is a classical clustering problem and has many applications in protein interaction networks, cross-lingual link detection, communication networks, etc. In this paper, we discuss the capacitated correlation clustering problem on labeled complete graphs, in which each edge is labeled + or - to indicate two endpoints are "similar" or "dissimilar", respectively. Our objective is to partition the vertex set into several clusters, subject to an upper bound on cluster size, so as to minimize the number of disagreements. Here the number of disagreements is defined as the total number of the edges with positive labels between clusters and the edges with negative labels within clusters. The main contribution of this work is providing a 5.37-approximation algorithm for the capacitated correlation clustering problem, improving the current best approximation ratio of 6 [21]. In addition, we have conducted a series of numerical experiments, which effectively demonstrate the effectiveness of our algorithm.

Keyword:

LP-rounding Correlation clustering Capacitated correlation clustering Approximation algorithm

Author Community:

  • [ 1 ] [Ji, Sai]Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China
  • [ 2 ] [Cheng, Yukun]Suzhou Univ Sci & Technol, Suzhou 215009, Peoples R China
  • [ 3 ] [Tan, Jingjing]Weifang Univ, Sch Math & Informat Sci, Weifang 261061, Peoples R China
  • [ 4 ] [Zhao, Zhongrui]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China

Reprint Author's Address:

Show more details

Related Keywords:

Related Article:

Source :

COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2021

ISSN: 0302-9743

Year: 2021

Volume: 13135

Page: 35-45

Cited Count:

WoS CC Cited Count: 1

SCOPUS Cited Count: 1

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 3

Affiliated Colleges:

Online/Total:862/10801434
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.