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 |