A note on Probably Certifiably Correct algorithms
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). First posted on arXiv 2 Sep 2015.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 4; 2022: 4; 2023: 0; 2024: 1.
9 papers.
- 2021Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimizationcited by 21
- 2021Advances in Inference and Representation for Simultaneous Localization and Mappingcited by 16
- 2021Optimal Pose and Shape Estimation for Category-level 3D Object Perceptioncited by 15
- 2022ARCS: Accurate Rotation and Correspondence Searchcited by 15
- 2022Certifiable 3D Object Pose Estimation: Foundations, Learning Models, and Self-Trainingcited by 12
- 2022Optimal and Robust Category-level Perception: Object Pose and Shape Estimation from 2D and 3D Semantic Keypointscited by 7
- 2021Fast and Robust Certifiable Estimation of the Relative Pose Between Two Calibrated Camerascited by 5
- 2024CLIPPER: Robust Data Association without an Initial Guesscited by 3
- 2022Sketch-and-solve approaches to k-means clustering by semidefinite programmingcited by 1
- 2024CLIPPER: Robust Data Association without an Initial Guess11 Feb 2024
- 2022Sketch-and-solve approaches to k-means clustering by semidefinite programming28 Nov 2022
- 2022Optimal and Robust Category-level Perception: Object Pose and Shape Estimation from 2D and 3D Semantic Keypoints24 Jun 2022
- 2022Certifiable 3D Object Pose Estimation: Foundations, Learning Models, and Self-Training22 Jun 2022
- 2022ARCS: Accurate Rotation and Correspondence Search28 Mar 2022
- 2021Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization7 Sep 2021
- 2021Optimal Pose and Shape Estimation for Category-level 3D Object Perception16 Apr 2021
- 2021Advances in Inference and Representation for Simultaneous Localization and Mapping8 Mar 2021
- 2021Fast and Robust Certifiable Estimation of the Relative Pose Between Two Calibrated Cameras21 Jan 2021