A note on probably certifiably correct algorithms

DOI10.1016/J.CRMA.2015.11.009MaRDI QIDQ1695210zbMATH OpenOpenAlexFDO

Authors Afonso S. Bandeira

Publication date 7 February 2018

Published in Comptes Rendus. Mathématique. Académie des Sciences, Paris (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.00824

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Abstract computational complexity for mathematical programming problems (90C60)

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.

Recommendations

• Probably certifiably correct k-means clustering
• Combinational optimization problems for which almost every algorithm is asymptotically optimal
• A proof of the block model threshold conjecture
• scientific article; zbMATH DE number 1418276
• Certifying algorithms

Cites work

• Complementarity and nondegeneracy in semidefinite programming
• Compressed sensing
• Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
• Exact Recovery in the Stochastic Block Model
• High-dimensional analysis of semidefinite relaxations for sparse principal components
• Relax, no need to round: integrality of clustering formulations
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Sum-of-squares proofs and the quest toward optimal algorithms
• Theory of semidefinite programming for sensor network localization
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization

Cited in

(7)

• Probably certifiably correct k-means clustering
• On semidefinite relaxations for the block model
• Fast and robust certifiable estimation of the relative pose between two calibrated cameras
• Scalable low-rank semidefinite programming for certifiably correct machine perception
• Fast certifiable relative pose estimation with gravity prior
• The Lovász theta function for recovering planted clique covers and graph colorings
• A semidefinite relaxation for sums of heterogeneous quadratic forms on the Stiefel manifold

This page was built for publication: A note on probably certifiably correct algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1695210)