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

Author:

Ji, Sai (Ji, Sai.) | Dong, Yinhong (Dong, Yinhong.) | Du, Donglei (Du, Donglei.) | Wang, Dongzhao (Wang, Dongzhao.) | Xu, Dachuan (Xu, Dachuan.) (Scholars:徐大川)

Indexed by:

EI Scopus SCIE

Abstract:

Lower bounded correlation clustering problem (LBCorCP) is a new generalization of the correlation clustering problem (CorCP). In the LBCorCP, we are given an integer L and a complete labelled graph. Each edge in the graph is either positive or negative based on the similarity of its two endpoints. The goal is to find a clustering of the vertices, each cluster contains at least L vertices, so as to minimize the sum of the number of positive cut edges and negative uncut edges. In this paper, we first introduce the LBCorCP and give three algorithms for this problem. The first algorithm is a random algorithm, which is designed for the instances of the LBCorCP with fewer positive edges. The second one is that we let the set V itself as a cluster and prove that the algorithm works well on two specially instances with fewer negative edges. The last one is an LP-rounding based iterative algorithm, which is also provided for the instances with fewer negative edges. The above three algorithms can quickly solve some special instances in polynomial time and obtain a smaller approximation ratio. In addition, we conduct simulations to evaluate the performance of our algorithms.

Keyword:

Correlation clustering Lower bounded LP-rounding Approximation algorithm Polynomial time

Author Community:

  • [ 1 ] [Ji, Sai]Hebei Univ Technol, Inst Math, Tianjin 300401, Peoples R China
  • [ 2 ] [Dong, Yinhong]Hainan Univ, Sch Publ Adm, Haikou 570228, Hainan, Peoples R China
  • [ 3 ] [Du, Donglei]Univ New Brunswick, Fac Business Adm, Fredericton, NB E3B 5A3, Canada
  • [ 4 ] [Wang, Dongzhao]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 5 ] [Xu, Dachuan]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China

Reprint Author's Address:

  • [Xu, Dachuan]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China;;

Show more details

Related Keywords:

Related Article:

Source :

JOURNAL OF COMBINATORIAL OPTIMIZATION

ISSN: 1382-6905

Year: 2023

Issue: 1

Volume: 45

1 . 0 0 0

JCR@2022

ESI Discipline: MATHEMATICS;

ESI HC Threshold:9

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: 2

Affiliated Colleges:

Online/Total:804/10649406
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.