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

Author:

Ji, Sai (Ji, Sai.) | Li, Gaidi (Li, Gaidi.) | Zhang, Dongmei (Zhang, Dongmei.) | Zhang, Xianzhao (Zhang, Xianzhao.)

Indexed by:

EI Scopus

Abstract:

Correlation clustering problem is an elegant clustering problem and has many applications in protein interaction networks, cross-lingual link detection, etc. In this paper, we introduce the capacitated correlation clustering problem with penalties by combining the capacitated correlation clustering problem and the correlation problem with penalties. There are two main contributions in this paper. The first one is that we give an integer programming for the capacitated correlation clustering problem with penalties. The second one is that we provide an LP-based (4 / (4 - 5 α), 8 / α) -bi-criteria approximation algorithm for this problem, where parameter α∈ (0, 4 / 9 ]. © 2021, Springer Nature Switzerland AG.

Keyword:

Approximation algorithms Integer programming Clustering algorithms

Author Community:

  • [ 1 ] [Ji, Sai]Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing; 100190, China
  • [ 2 ] [Li, Gaidi]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing; 100124, China
  • [ 3 ] [Zhang, Dongmei]School of Computer Science and Technology, Shandong Jianzhu University, Jinan; 250101, China
  • [ 4 ] [Zhang, Xianzhao]School of Mathematics and Statistics, Linyi University, Linyi; 276005, China

Reprint Author's Address:

Email:

Show more details

Related Keywords:

Source :

ISSN: 0302-9743

Year: 2021

Volume: 13153 LNCS

Page: 15-26

Language: English

Cited Count:

WoS CC Cited Count:

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:1397/10902096
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.