Fetching the paper…

Reading the bibliography…

2015

A note on Probably Certifiably Correct algorithms

Bandeira, Afonso S.

Original
PDF
Post on X

Understand

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.

A note on Probably Certifiably Correct algorithms · Around

Built on

G. Stengle
1974
Earlier work this paper cites.
J. Kuczynski and H. Wozniakowski
1992
Earlier work this paper cites.
M. X. Goemans and D. P. Williamson
1995
Earlier work this paper cites.
L. Vanderberghe and S. Boyd
1996
Earlier work this paper cites.
F. Alizadeh, J.-P. Haeberly, and M. Overton
1997
Earlier work this paper cites.
Y. Nesterov
2000
Earlier work this paper cites.
P. A. Parrilo
2000
Earlier work this paper cites.
U. Feige and J. Kilian
2001
Earlier work this paper cites.
J. B. Lassere
2001
Earlier work this paper cites.
F. McSherry
2001
Earlier work this paper cites.
E. J. Candès, J. Romberg, and T. Tao
2006
Earlier work this paper cites.
D. L. Donoho
2006
Earlier work this paper cites.
P. V. R. Gribonval, R. M. F. I Ventura
2006
Earlier work this paper cites.
A. M.-C. So and Y. Ye
2006
Earlier work this paper cites.

Similar

A. A. Amini and M. J. Wainwright
2009
Cited alongside, same era.
E. Candès and B. Recht
2009
Cited alongside, same era.
A. M.-C. So
2010
Cited alongside, same era.
D. P. Williamson and D. B. Shmoys
Original
2011
Cited alongside, same era.
E. J. Candès, T. Strohmer, and V. Voroninski
2013
Cited alongside, same era.
P. Jain, P. Netrapalli, and S. Sanghavi
2013
Cited alongside, same era.
E. Abbe, A. S. Bandeira, A. Bracher, and A. Singer
2014
Cited alongside, same era.

Then

B. Hajek, Y. Wu, and J. Xu
Original
2014
Later among the works it cites.
A. Montanari and E. Richard
Original
2014
Later among the works it cites.
E. Mossel, J. Neeman, and A. Sly
Original
2014
Later among the works it cites.
E. Abbe and C. Sandon
Original
2015
Closest in time.
N. Agarwal, A. S. Bandeira, K. Koiliaris, and A. Kolla
Original
2015
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

E. Abbe, A. S. Bandeira, and G. Hall

2014

Cited alongside, same era.

A. S. Bandeira, N. Boumal, and A. Singer

2014

Cited alongside, same era.

A. S. Bandeira, M. Charikar, A. Singer, and A. Zhu

2014

Cited alongside, same era.

A. S. Bandeira, Y. Khoo, and A. Singer

2014

Cited alongside, same era.

B. Barak and D. Steurer

2014

Cited alongside, same era.

P. Awasthi, A. S. Bandeira, M. Charikar, R. Krishnaswamy, S. Villar, and R. Ward

2015

Closest in time.

2015

Closest in time.

A. S. Bandeira, Y. Chen, and A. Singer

2015

Closest in time.

L. Carlone, D. Rosen, G. Calafiore, J. Leonard, and F. Dellaert

2015

Closest in time.

S. B. Hopkins, J. Shi, and D. Steurer

2015

Closest in time.

T. Iguchi, D. G. Mixon, J. Peterson, and S. Villar

2015

Closest in time.

W. Perry and A. S. Wein

2015

Closest in time.

E. J. Candes and T. Tao

2080

Closest in time.