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

Abstract:

This paper considers the capacitated correlation clustering problem with penalties (CCorCwP), which is a new generalization of the correlation clustering problem. In this problem, we are given a complete graph, each edge is either positive or negative. Moreover, there is an upper bound on the number of vertices in each cluster, and each vertex has a penalty cost. The goal is to penalize some vertices and select a clustering of the remain vertices, so as to minimize the sum of the number of positive cut edges, the number of negative non-cut edges and the penalty costs. In this paper we present an integer programming, linear programming relaxation and two polynomial time algorithms for the CCorCwP. Given parameter delta is an element of (0, 4/9], the first algorithm is a (8/(4 - 5 delta), 8/delta)-N-criteria approximation algorithm for the CCorCPwP, which means that the number of vertices in each cluster does not exceed 8/(4 - 5 delta) times the upper bound, and the output objective function value of the algorithm does not exceed 8/delta times the optimal value. The second one is based on above bi-criteria approximation, and we prove that the second algorithm can achieve a constant approximation ratio for some special instances of the CCorCwP.

Keyword:

Capacitated Correlation clustering LP-rounding Penalties Approximation algorithm

Author Community:

  • [ 1 ] [Ji, Sai]Hebei Univ Technol, Inst Math, Tianjin 300401, Peoples R China
  • [ 2 ] [Li, Gaidi]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China
  • [ 3 ] [Zhang, Dongmei]Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China
  • [ 4 ] [Zhang, Xianzhao]Linyi Univ, Sch Math & Stat, Linyi 276005, Shandong, Peoples R China

Reprint Author's Address:

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

Show more details

Related Keywords:

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

SCOPUS Cited Count: 3

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 7

Affiliated Colleges:

Online/Total:351/10642520
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.