期刊
COMPTES RENDUS MATHEMATIQUE
卷 354, 期 3, 页码 329-333出版社
ACAD SCIENCES
DOI: 10.1016/j.crma.2015.11.009
关键词
-
类别
资金
- AFOSR [FA9550-12-1-0317]
- NSF [DMS-1317308]
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. (c) 2015 Academie des sciences. Published by Elsevier Masson SAS. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据