In this problem I'm given a Graph G = (V,E), the goal is to find a coloring of graph's vertices with 3 colors possible that maximize the quality function
q(c) = the number of edges that their endpoints are colored differently.
Give a probalistic 3/2 approximation, and show that the algorithm returns fail (meaning worse approximation) with probability at most d^-k for each natural number k and for a fixed d>= 1.
Now I've given this following algorithm: I color each vertex at random, that means the expected probability of an edge to have different color edges is 2/3 which makes it 3/2 approximation.
Yet, I've no idea how to show that it returns fail with probability of at most d^-k.
Could use some help, thanks!
Rather than try to untangle the quantifiers here, I'll just observe that the method of conditional expectations can be used to prove the following deterministically implementable greedy algorithm correct.
While there exists an uncolored vertex, color it one of the colors that appears least among its neighbors.
The idea is that each edge with an uncolored endpoint is worth 2/3 in expectation regardless of what other choices have been made, assuming that we color the rest of the graph randomly. By using the most diverse choice, we get at least as much deterministic value as we lost in randomized value.