Maximization problem

Question

I work at a company and i got to a seminar we're they told us to solve this problem below in the picture

Is there an algorithm that can help me solve this question. I thought about a randomized algorithm after that i get stuck?

Answer 1

The case $k \ge n$ is trivial as you can give different value to every variable, which satisfy all inequalities and thus is optimal. So let's consider $k < n$.

This problem can be considered as building a paritition of the $n$ variables in $k$ subsets. All inequalities involving two variables in the same subset are unsatisfied, any other is satisfied. I would first build an efficient structure to count the number of inequalities involving each pair of variables. Basically this is a $n^2$ array, built in $O(m)$. In case $m << n$, a graph may be more efficient than a sparse matrix.

Then, let's take arbitrarily $k$ variables and distribute them into the $k$ subsets (give them the $k$ different values). Any inequalities involving these first variables is satisfied (then the arbitrarily may target greedily the largest values in the array).

Then loop on the remaining variables. For each $x_i$, evaluate $A^i_k$, the number of unsatisfied inequalities (considering only the variables assigned so far), for each of the $k$ possible assignment. For this, one has to consider every assigned variable in the same subset, this step is $O(n)$.

Let's call $S_i = \sum_k A^i_k$.

By assigning $k_0$ to $x_i$,

you unsatisfy $A^i_{k_0}$ inequalities but satisfy $S_i - A^i_{k_0}$ ones.

So by picking $k_0$ that minimizes $A^i_{k_0}$, you unsatisfy at most $S/k$ inequalities, satisying at least $S(1-1/k)$ others. So overall you guarantee to satisfy $m(1-1/k)$ inequalities (and clearly $(1-1/k)OPT$ ones).

This achieves $O(m + n^2)$ in time and $O(n^2)$ in space.

Answer 2

Your problem is known as MAX-$k$-CUT, a generalization of the well-known MAX-CUT problem. A recent paper on the topic is Alantha Newman, Complex semidefinite programming and Max-$k$-Cut.

The classic algorithm of Goemans and Williamson gives a (roughly) 0.878 approximation for MAX-CUT (the case $k=2$ of your problem), which is tight assuming Khot's Unique Games Conjecture. The best possible approximation ratio (assuming the Unique Games Conjecture) for $k > 2$ is not yet known, as far as I understand, but it is known to be better than $1-1/k$ for all $k$.

A random assignment satisfies in expectation a $1-1/k$ fraction of the constraints, and in particular gives a $1-1/k$ approximation in expectation. This algorithm can be derandomized using the method of conditional expectations, as well as using the greedy approach outlined in Optidad's answer.