Skip to main content

Research Repository

Advanced Search

Suboptimality of local algorithms for a class of max-cut problems

Chen, Wei-Kuo; Gamarnik, David; Panchenko, Dmitry; Rahman, Mustazee

Suboptimality of local algorithms for a class of max-cut problems Thumbnail


Authors

Wei-Kuo Chen

David Gamarnik

Dmitry Panchenko



Abstract

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.

Citation

Chen, W., Gamarnik, D., Panchenko, D., & Rahman, M. (2019). Suboptimality of local algorithms for a class of max-cut problems. Annals of Probability, 47(3), 1587-1618. https://doi.org/10.1214/18-aop1291

Journal Article Type Article
Acceptance Date May 25, 2018
Online Publication Date May 2, 2019
Publication Date 2019-05
Deposit Date Sep 25, 2019
Publicly Available Date Mar 28, 2024
Journal Annals of Probability
Print ISSN 0091-1798
Publisher Institute of Mathematical Statistics
Peer Reviewed Peer Reviewed
Volume 47
Issue 3
Pages 1587-1618
DOI https://doi.org/10.1214/18-aop1291

Files




You might also like



Downloadable Citations