首页|Robust Correlation Clustering Problem with Locally Bounded Disagreements

Robust Correlation Clustering Problem with Locally Bounded Disagreements

扫码查看
原文链接
  • NETL
  • NSTL
  • 万方数据
Min-max disagreements are an important generalization of the correlation clustering problem(CorCP).It can be defined as follows.Given a marked complete graph G=(V,E),each edge in the graph is marked by a positive label"+"or a negative label"-"based on the similarity of the connected vertices.The goal is to find a clustering C of vertices V,so as to minimize the number of disagreements at the vertex with the most disagreements.Here,the disagreements are the positive cut edges and the negative non-cut edges produced by clustering C.This paper considers two robust min-max disagreements:min-max disagreements with outliers and min-max disagreements with penalties.Given parameter 8 e(0,1/14),we first provide a threshold-based iterative clustering algorithm based on LP-rounding technique,which is a(1/8,7/(1-14δ))-bi-criteria approximation algorithm for both the min-max disagreements with outliers and the min-max disagreements with outliers on one-sided complete bipartite graphs.Next,we verify that the above algorithm can achieve an approximation ratio of 21 for min-max disagreements with penalties when we set parameter 8=1/21.

min-max disagreementsoutlierspenaltiesapproximation algorithmLP-rounding

Sai Ji、Min Li、Mei Liang、Zhenning Zhang

展开 >

Institute of Mathematics,Hebei University of Technology,Tianjin 300401,China

School of Mathematics and Statistics,Shandong Normal University,Jinan 250358,China

College of Statistics and Data Science,Beijing University of Technology,Beijing 100124,China

Department of Operations Research and Information Engineering,Beijing University of Technology,Beijing 100124,China

展开 >

Science and Technology Project of Hebei Education DepartmentNational Natural Science Foundation of ChinaNational Natural Science Foundation of ChinaNational Natural Science Foundation of ChinaNatural Science Foundation of Shandong Province of China

BJK2023076121015941200102512131003ZR2020MA029

2024

10.26599/TST.2023.9010027

清华大学学报自然科学版(英文版)
清华大学

清华大学学报自然科学版(英文版)

CSTPCDEI
影响因子：0.474
ISSN：1007-0214
年,卷(期)：2024.29(1)
  • 23