Open Access Issue
Approximating (mB,mP)-Monotone BP Maximization and Extensions
Tsinghua Science and Technology 2023, 28 (5): 906-915
Published: 19 May 2023

The paper proposes the optimization problem of maximizing the sum of suBmodular and suPermodular (BP) functions with partial monotonicity under a streaming fashion. In this model, elements are randomly released from the stream and the utility is encoded by the sum of partial monotone suBmodular and suPermodular functions. The goal is to determine whether a subset from the stream of size bounded by parameter k subject to the summarized utility is as large as possible. In this work, a threshold-based streaming algorithm is presented for the BP maximization that attains a ((1-κ)/(2-κ)-𝒪(ε))-approximation with 𝒪(1/ε4log3(1/ε)log((2-κ)k/(1-κ)2)) memory complexity, where κ denotes the parameter of supermodularity ratio. We further consider a more general model with fair constraints and present a greedy-based algorithm that obtains the same approximation. We finally investigate this fair model under the streaming fashion and provide a ((1-κ)4/(2-2κ+κ2)2-𝒪(ε))-approximation algorithm.

Open Access Issue
Approximation Algorithm for the Balanced 2-Correlation Clustering Problem
Tsinghua Science and Technology 2022, 27 (5): 777-784
Published: 17 March 2022

The Correlation Clustering Problem (CorCP) is a significant clustering problem based on the similarity of data. It has significant applications in different fields, such as machine learning, biology, and data mining, and many different problems in other areas. In this paper, the Balanced 2-CorCP (B 2-CorCP) is introduced and examined, and a new interesting variant of the CorCP is described. The goal of this clustering problem is to partition the vertex set into two clusters with equal size, such that the number of disagreements is minimized. We first present a polynomial time algorithm for the B 2-CorCP on M-positive edge dominant graphs (M3). Then, we provide a series of numerical experiments, and the results show the effectiveness of our algorithm.

total 2