Slicing graphs

We define a slice in a graph \(G=(V,E)\) as a partition of \(V\) into two non-intersecting sets \(A\) and \(B\). An edge of \(G\) is said to be sliced if one of its ends is in \(A\) and the other is in \(B\). Suppose that we want to maximize the number of edges that have been sliced. We use the following approximation algorithm :

Assign every vertex \(v \in V\) to \(A\), \(B\) uniformly at random.

The randomized algorithm has no more than \(n\) times worse than the optimum in expectation. What is \(n\)?

×

Problem Loading...

Note Loading...

Set Loading...