EUVIMEDEUVIMED entdecken
Crossref

Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree

Ahmed El Alaoui, Andrea Montanari, Mark Sellke

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →