Content deleted Content added
RezaKhazar (talk | contribs) |
RezaKhazar (talk | contribs) |
||
Line 41:
In principle, exact recovery can be solved in its feasible range using [[maximum likelihood]], but this amounts to solving a constrained or [[Regularization (mathematics)|regularized]] cut problem such as minimum bisection that is typically [[NP-complete]]. Hence, no known efficient algorithms will correctly compute the maximum-likelihood estimate in the worst case.
However, a wide variety of algorithms perform well in the average case, and many high-probability performance guarantees have been proven for algorithms in both the partial and exact recovery settings. Successful algorithms include [[spectral clustering]] of the vertices,<ref name="krzakala-pnas"/><ref name="mas13" /><ref name="as15a" /><ref name="lr15" /> [[semidefinite programming]],<ref name="al14" /><ref name="abh14" />, forms of [[belief propagation]],<ref name="decelle11"/><ref name="mns13" />, and
== Variants ==
| |||