A note on probably certifiably correct algorithms

Afonso S. Bandeira

doi:10.1016/j.crma.2015.11.009

A note on probably certifiably correct algorithms

Afonso S. Bandeira

Mathematics

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	329-333
Number of pages	5
Journal	Comptes Rendus Mathematique
Volume	354
Issue number	3
DOIs	https://doi.org/10.1016/j.crma.2015.11.009
State	Published - Mar 1 2016

ASJC Scopus subject areas

Mathematics(all)

Access to Document

10.1016/j.crma.2015.11.009

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

Cite this

@article{27f7544098e04f92acce97d9cbc39540,

title = "A note on probably certifiably correct algorithms",

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.",

author = "Bandeira, {Afonso S.}",

note = "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.",

year = "2016",

month = mar,

day = "1",

doi = "10.1016/j.crma.2015.11.009",

language = "English (US)",

volume = "354",

pages = "329--333",

journal = "Comptes Rendus Mathematique",

issn = "1631-073X",

publisher = "Elsevier Masson",

number = "3",

}

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.

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 -