Maximization problem
-
29-09-2020 - |
المحلول
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.
نصائح أخرى
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.