In this paper, we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone $k$-submodular function under a matroid constraint. In order to reduce the complexity of this algorithm, we also present a randomized 1/3-approximation algorithm with the probability of $1-\epsilon$, where $\epsilon$ is the probability of algorithm failure. Moreover, we design a streaming algorithm for both monotone and non-monotone objective $k$-submodular functions.

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}$.

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.