Suboptimality of local algorithms for a class of max-cut problems
© Institute of Mathematical Statistics, 2019. 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 freque...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Mathematical Statistics
2021
|
| Online Access: | https://hdl.handle.net/1721.1/134436 |
| _version_ | 1826189889564049408 |
|---|---|
| author | Chen, Wei-Kuo Gamarnik, David Panchenko, Dmitry Rahman, Mustazee |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Chen, Wei-Kuo Gamarnik, David Panchenko, Dmitry Rahman, Mustazee |
| author_sort | Chen, Wei-Kuo |
| collection | MIT |
| description | © Institute of Mathematical Statistics, 2019. 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 maxcut 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. |
| first_indexed | 2024-09-23T08:29:07Z |
| format | Article |
| id | mit-1721.1/134436 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:29:07Z |
| publishDate | 2021 |
| publisher | Institute of Mathematical Statistics |
| record_format | dspace |
| spelling | mit-1721.1/1344362023-09-28T20:18:01Z Suboptimality of local algorithms for a class of max-cut problems Chen, Wei-Kuo Gamarnik, David Panchenko, Dmitry Rahman, Mustazee Sloan School of Management Massachusetts Institute of Technology. Department of Mathematics © Institute of Mathematical Statistics, 2019. 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 maxcut 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. 2021-10-27T20:05:00Z 2021-10-27T20:05:00Z 2019 2021-04-15T17:41:29Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/134436 en 10.1214/18-AOP1291 The Annals of Probability Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Mathematical Statistics arXiv |
| spellingShingle | Chen, Wei-Kuo Gamarnik, David Panchenko, Dmitry Rahman, Mustazee Suboptimality of local algorithms for a class of max-cut problems |
| title | Suboptimality of local algorithms for a class of max-cut problems |
| title_full | Suboptimality of local algorithms for a class of max-cut problems |
| title_fullStr | Suboptimality of local algorithms for a class of max-cut problems |
| title_full_unstemmed | Suboptimality of local algorithms for a class of max-cut problems |
| title_short | Suboptimality of local algorithms for a class of max-cut problems |
| title_sort | suboptimality of local algorithms for a class of max cut problems |
| url | https://hdl.handle.net/1721.1/134436 |
| work_keys_str_mv | AT chenweikuo suboptimalityoflocalalgorithmsforaclassofmaxcutproblems AT gamarnikdavid suboptimalityoflocalalgorithmsforaclassofmaxcutproblems AT panchenkodmitry suboptimalityoflocalalgorithmsforaclassofmaxcutproblems AT rahmanmustazee suboptimalityoflocalalgorithmsforaclassofmaxcutproblems |