What's the deal with Deno? We talk with a major contributor to find out. Listen now.

# Tag Info

## 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