New answers tagged randomized-algorithms
0
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 ...
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 ...
1
You essentially want to generate a graph with some degree sequence (which you want to be random, but this is not relevant); this is called the graph realization problem which is solved e.g. by the Havel-Hakimi algorithm in the sense that the algorithm will return a (simple) graph with the desired degree sequence if that is possible (such sequences are called ...
2
The probability that the element $1$ belongs to a random $m$-subset of an $n$-element set is $m/n$. Therefore you should include $1$ in your subset with probability $m/n$.
If you put $1$ in your subset, then you are left with choosing an $(m-1)$-subset of an $(n-1)$-element set.
If you didn't put $1$ in your subset, then you are left with choosing an $m$-...
Top 50 recent answers are included
