Maximization problem
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 &lt; 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 &lt;&lt; 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.