All Questions
Tagged with max-cut optimization
2 questions
4
votes
1
answer
490
views
Intuitive explanation behind Goemans-Williamson randomized rounding
A very simple randomized cut algorithm achieves $1/2$ of the optimal value: just choose each vertex to be in the cut with probability $1/2$, independently. Goemans-Williamson does something more ...
- 10.6k
8
votes
3
answers
1k
views
Hardness of MAX-CUT on sparse graphs
Let a weighted graph $G(V,E)$, where the weights are real (positve and negative). Assume that $G$ has $\mathcal{O}(n\log n)$ edges.
How fast can we compute MAX-CUT on this graph?
Can we compute (...
- 1,356