feedback
Reputation: 3
Why in max-cut ( weigthted graph )we can't do an approximation lower than 1/2?
I have been trying to solve the Max-Cut problem using approximation algorithms, but I still don't get how the best approximation I can get is 1/2. I could use any help or paper of proof of this fact.
Upvotes: 0
Views: 92
Answers (0)
Related Questions
- Having trouble understanding the MAX-CUT problem
- Finding maximum ratio min cut in spanning tree of a graph
- Computing Min-Cut of a Graph with No Reverse Edges
- Why is the global min cut cardinality less than the degree of every vertex for network flows
- Number of min cuts in max flow
- Why is finding the maximum cut NP-hard?
- Max flow - Min cut theorem
- Graph Theory - globally minimal cut and its implications
- Minimum Cut by Karger MinCut Java Large Input Error
- How to increase the size of min-cut in graph by adding minimum number of edges