SUBOPTIMALITY OF LOCAL ALGORITHMS FOR A CLASS OF MAX-CUT PROBLEMS

被引：42

作者：

Chen, Wei-Kuo ^{[1
]}

Gamarnik, David ^{[3
]}

Panchenko, Dmitry ^{[2
]}

Rahman, Mustazee ^{[4
]}

机构：

[1] Univ Minnesota, Sch Math, Minneapolis, MN 55455 USA

[2] Univ Toronto, Dept Math, Toronto, ON, Canada

[3] MIT, Sloan Sch Management, Cambridge, MA 02139 USA

[4] MIT, Dept Math, Cambridge, MA 02139 USA

来源：

ANNALS OF PROBABILITY | 2019年 / 47卷 / 03期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Local algorithms; maximum cut problems; spin glasses; PARISI FORMULA; SPIN; BOUNDS; LIMITS; FIELDS;

D O I：

10.1214/18-AOP1291

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

We show that in random K-uniform hypergraphs of constant average degree, for even K >= 4, local algorithms defined as factors of i.i.d. can not find nearly maximal cuts, when the average degree is sufficiently large. These algorithms have been used frequently to obtain lower bounds for the max-cut problem on random graphs, but it was not known whether they could be successful in finding nearly maximal cuts. This result follows from the fact that the overlap of any two nearly maximal cuts in such hypergraphs does not take values in a certain nontrivial interval-a phenomenon referred to as the overlap gap property-which is proved by comparing diluted models with large average degree with appropriate fully connected spin glass models and showing the overlap gap property in the latter setting.

引用

页码：1587 / 1618

页数：32

共 44 条

[21] The high temperature region of the Viana-Bray diluted spin glass model [J].