Open Access Issue
Robust Correlation Clustering Problem with Locally Bounded Disagreements
Tsinghua Science and Technology 2024, 29 (1): 66-75
Published: 21 August 2023

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 𝒞 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 𝒞. This paper considers two robust min-max disagreements: min-max disagreements with outliers and min-max disagreements with penalties. Given parameter δ(0,1/14), we first provide a threshold-based iterative clustering algorithm based on LP-rounding technique, which is a (1/δ,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 δ=1/21.

Open Access Issue
k-Submodular Maximization with a Knapsack Constraint and p Matroid Constraints
Tsinghua Science and Technology 2023, 28 (5): 896-905
Published: 19 May 2023

A k-submodular function is a generalization of a submodular function, its definition domain is extended from the collection of single subsets to the collection of k disjoint subsets. The k-submodular maximization problem has a wide range of applications. In this paper, we propose a nested greedy and local search algorithm for the problem of maximizing a monotone k-submodular function subject to a knapsack constraint and p matroid constraints.

total 2