TY - JOUR
T1 - A note on probably certifiably correct algorithms
AU - Bandeira, Afonso S.
N1 - 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
SN - 1631-073X
VL - 354
SP - 329
EP - 333
JO - Comptes Rendus Mathematique
JF - Comptes Rendus Mathematique
IS - 3
ER -