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