In this paper, we study a class of online continuous optimization problems. At each round, the utility function is the sum of a weakly diminishing-returns (DR) submodular function and a concave function, certain cost associated with the action will occur, and the problem has total limited budget. Combining the two methods, the penalty function and Frank-Wolfe strategies, we present an online method to solve the considered problem. Choosing appropriate stepsize and penalty parameters, the performance of the online algorithm is guaranteed, that is, it achieves sub-linear regret bound and certain mild constraint violation bound in expectation.

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\mathrm{=}\mathrm{(}V\mathrm{,}E\mathrm{)}$, each edge in the graph is marked by a positive label " $\mathrm{+}$" or a negative label " $\mathrm{-}$" 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 $\delta \mathrm{\in }\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{/}\mathrm{14}\mathrm{)}$, we first provide a threshold-based iterative clustering algorithm based on LP-rounding technique, which is a $\mathrm{(}\mathrm{1}\mathrm{/}\delta \mathrm{,}\mathrm{7}\mathrm{/}\mathrm{(}\mathrm{1}\mathrm{-}\mathrm{14}\mathsf{}\delta \mathrm{)}\mathrm{)}$-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 $\mathrm{21}$ for min-max disagreements with penalties when we set parameter $\delta \mathrm{=}\mathrm{1}\mathrm{/}\mathrm{21}$.

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.

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 $\mathrm{(}\mathrm{1}\mathrm{/}\mathrm{3}\mathrm{,}\mathrm{2}\mathrm{/}\mathrm{3}\mathrm{)}$-approximation for the problem is provided.