A note on probably certifiably correct algorithms

Afonso S. Bandeira

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)329-333
Number of pages5
JournalComptes Rendus Mathematique
Volume354
Issue number3
DOIs
StatePublished - Mar 1 2016

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'A note on probably certifiably correct algorithms'. Together they form a unique fingerprint.

Cite this