TY - JOUR
T1 - A note on probably certifiably correct algorithms
AU - Bandeira, Afonso S.
N1 - Funding Information:
A.S. Bandeira was partially supported by AFOSR Grant No. FA9550-12-1-0317 and NSF grant DMS-1317308 . Part of this work was done while the author was at Princeton University.
Publisher Copyright:
© 2015 Académie des sciences.
PY - 2016/3/1
Y1 - 2016/3/1
N2 - Many optimization problems of interest are known to be intractable, and while there are often heuristics that are known to work on typical instances, it is usually not easy to determine a posteriori whether the optimal solution was found. In this short note, we discuss algorithms that not only solve the problem on typical instances, but also provide a posteriori certificates of optimality, probably certifiably correct (PCC) algorithms. As an illustrative example, we present a fast PCC algorithm for minimum bisection under the stochastic block model and briefly discuss other examples.
AB - Many optimization problems of interest are known to be intractable, and while there are often heuristics that are known to work on typical instances, it is usually not easy to determine a posteriori whether the optimal solution was found. In this short note, we discuss algorithms that not only solve the problem on typical instances, but also provide a posteriori certificates of optimality, probably certifiably correct (PCC) algorithms. As an illustrative example, we present a fast PCC algorithm for minimum bisection under the stochastic block model and briefly discuss other examples.
UR - http://www.scopus.com/inward/record.url?scp=84958856593&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958856593&partnerID=8YFLogxK
U2 - 10.1016/j.crma.2015.11.009
DO - 10.1016/j.crma.2015.11.009
M3 - Article
AN - SCOPUS:84958856593
VL - 354
SP - 329
EP - 333
JO - Comptes Rendus Mathematique
JF - Comptes Rendus Mathematique
SN - 1631-073X
IS - 3
ER -