We consider the Max Directed 3-Section problem, which is closely connected to other well-known graph partition problems, such as Max Cut and Max Bisection. Given an arc-weighted directed graph, the goal of the Max Directed 3-Section problem is to partition the vertex set into three disjoint subsets with equal size, while maximizing the total weight of arcs crossing different vertex subsets. By combining the Lasserre hierarchy with the random hyperplane rounding strategy, we propose a polynomial-time algorithm with approximation ratio of 0.489.

Submodular function maximization problem has been extensively studied recently. A natural variant of submodular function is k-submodular function, which has many applications in real life, such as influence maximization and sensor placement problem. The domain of a k-submodular function has k disjoint subsets, and hence includes submodular function as a special case when k=1. This work investigates the k-submodular function maximization problem with d-knapsack constraints over the sliding window. Based on the smooth histogram technique, we design a deterministic approximation algorithm. Furthermore, we propose a randomized algorithm to improve the approximation ratio.

This paper studies two scheduling games on identical batching-machines with activation cost, where each game comprises $n$ jobs being processed on $m$ identical batching-machines. Each job, as an agent, chooses a machine (or, more accurately, a batch on a machine) for processing in order to minimize its disutility, which is comprised of its machine’s load and the activation cost it shares. Based on previous results, we present the Mixed strategy Nash Equilibria (MNE) for some special cases of the two games. For each game, we first analyze the conditions for the nonexistence of Nash equilibrium, then provide the MNE for the conditions, and offer the efficiency of MNE (mixed price of anarchy).

Two-stage submodular maximization problem under cardinality constraint has been widely studied in machine learning and combinatorial optimization. In this paper, we consider knapsack constraint. In this problem, we give $n$ articles and $m$ categories, and the goal is to select a subset of articles that can maximize the function $F(S)$. Function $F(S)$ consists of $m$ monotone submodular functions $f_j$, $j=1,2,\dots ,m$, and each $f_j$ measures the similarity of each article in category $j$. We present a constant-approximation algorithm for this problem.

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.

The clustering problem of big data in the era of artificial intelligence has been widely studied. Because of the huge amount of data, distributed algorithms are often used to deal with big data problems. The distributed computing model has an attractive feature: it can handle massive datasets that cannot be put into the main memory. On the other hand, since many decisions are made automatically by machines in today’s society, algorithm fairness is also an important research area of machine learning. In this paper, we study two fair clustering problems: the centralized fair $k$-center problem with outliers and the distributed fair $k$-center problem with outliers. For these two problems, we have designed corresponding constant approximation ratio algorithms. The theoretical proof and analysis of the approximation ratio, and the running space of the algorithm are given.

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 $\mathrm{2}$-CorCP (B $\mathrm{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 $\mathrm{2}$-CorCP on $M$-positive edge dominant graphs $\mathrm{(}M\mathrm{⩾}\mathrm{3}\mathrm{)}$. Then, we provide a series of numerical experiments, and the results show the effectiveness of our algorithm.