Motwani & Raghavan (Maximum Cut, Approximate Maximum Cut)
Jump to navigation
Jump to search
Time Complexity
$O(n)$?
Space Complexity
$O(n)$ words
(Keeps track of current coloring/random assignment)
Description
Approximate?
Approximate
Approximation Factor: 0.5
Randomized?
Yes, Monte Carlo
Model of Computation
Word RAM
Year
1995
Reference
https://rajsain.files.wordpress.com/2013/11/randomized-algorithms-motwani-and-raghavan.pdf