Abstract
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.
基金项目
Science and Technology Project of Hebei Education Department(BJK2023076)
National Natural Science Foundation of China(12101594)
National Natural Science Foundation of China(12001025)
National Natural Science Foundation of China(12131003)
Natural Science Foundation of Shandong Province of China(ZR2020MA029)
NETL
NSTL
万方数据