A greedy approximation algorithm for max k-cut
The natural greedy approach goes roughly like this:


  Go over the vertices one by one. For each one, allocate it to a part in a way maximizing the total cost of edges cut.


There are at least two natural ways of defining total cost of edges cut:


Total cost of edges between the vertex and vertices already allocated to different partitions.
Same as 1, together with the expected cost of cut edges to vertices not already allocated.


In this case both ways are the same, but the second shows the connection between the greedy algorithm and the trivial randomized algorithm, which allocates the vertices completely randomly.