Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree
Random Structures & Algorithms · 2023-10 · 63 (3) · 689-715
DOI: 10.1002/rsa.21149 ↗Kurz gefasst
Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 10.05.2023. Verfasst von Ahmed El Alaoui und 2 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 25 Literaturangaben. Gefördert von: National Science Foundation, Office of Naval Research.
Abstract (Originalsprache)
Given a graph of degree over vertices, we consider the problem of computing a near maximum cut or a near minimum bisection in polynomial time. For graphs of girth , we develop a local message passing algorithm whose complexity is , and that achieves near optimal cut values among all ‐local algorithms. Focusing on max‐cut, the algorithm constructs a cut of value , where is the value of the Parisi formula from spin glass theory, and (subscripts indicate the asymptotic variables). Our result generalizes to locally treelike graphs, that is, graphs whose girth becomes after removing a small fraction of vertices. Earlier work established that, for random ‐regular graphs, the typical max‐cut value is . Therefore our algorithm is nearly optimal on such graphs. An immediate corollary of this result is that random regular graphs have nearly minimum max‐cut, and nearly maximum min‐bisection among all regular locally treelike graphs. This can be viewed as a combinatorial version of the near‐Ramanujan property of random regular graphs.
Förderung
- National Science Foundation
- Office of Naval Research
Zitieren
APA
Alaoui, A. E., Montanari, A., & Sellke, M. (2023). Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree. Random Structures & Algorithms, 63(3), 689-715. https://doi.org/10.1002/rsa.21149
Vancouver
Alaoui AE, Montanari A, Sellke M. Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree. Random Structures & Algorithms. 2023;63(3):689-715. doi:10.1002/rsa.21149
BibTeX
@article{Alaoui2023,
author = {Alaoui, Ahmed El and Montanari, Andrea and Sellke, Mark},
title = {Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree},
journal = {Random Structures & Algorithms},
year = {2023},
volume = {63},
number = {3},
pages = {689--715},
doi = {10.1002/rsa.21149}
}
EUVIMED