Open Access Issue
Maximizing Submodular+Supermodular Functions Subject to a Fairness Constraint
Tsinghua Science and Technology 2024, 29 (1): 46-55
Published: 21 August 2023
Abstract PDF (1.4 MB) Collect

We investigate the problem of maximizing the sum of submodular and supermodular functions under a fairness constraint. This sum function is non-submodular in general. For an offline model, we introduce two approximation algorithms: A greedy algorithm and a threshold greedy algorithm. For a streaming model, we propose a one-pass streaming algorithm. We also analyze the approximation ratios of these algorithms, which all depend on the total curvature of the supermodular function. The total curvature is computable in polynomial time and widely utilized in the literature.

Open Access Issue
A Note on Maximizing Regularized Submodular Functions Under Streaming
Tsinghua Science and Technology 2023, 28 (6): 1023-1029
Published: 28 July 2023
Abstract PDF (413 KB) Collect

Recent progress in maximizing submodular functions with a cardinality constraint through centralized and streaming modes has demonstrated a wide range of applications and also developed comprehensive theoretical guarantees. The submodularity was investigated to capture the diversity and representativeness of the utilities, and the monotonicity has the advantage of improving the coverage. Regularized submodular optimization models were developed in the latest studies (such as a house on fire), which aimed to sieve subsets with constraints to optimize regularized utilities. This study is motivated by the setting in which the input stream is partitioned into several disjoint parts, and each part has a limited size constraint. A first threshold-based bicriteria (1/3,2/3)-approximation for the problem is provided.

Total 2