2026-07-24T00:34:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11192 2024-03-06T10:47:40Z ddc:004 open_access

Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem Li, Huan Sun, He Zanetti, Luca Spectral methods Hermitian Laplacians the Max-2-Lin problem Unique Games We study spectral approaches for the MAX-2-LIN(k) problem, in which we are given a system of m linear equations of the form x_i - x_j is equivalent to c_{ij} mod k, and required to find an assignment to the n variables {x_i} that maximises the total number of satisfied equations. We consider Hermitian Laplacians related to this problem, and prove a Cheeger inequality that relates the smallest eigenvalue of a Hermitian Laplacian to the maximum number of satisfied equations of a MAX-2-LIN(k) instance I. We develop an O~(kn^2) time algorithm that, for any (1-epsilon)-satisfiable instance, produces an assignment satisfying a (1 - O(k)sqrt{epsilon})-fraction of equations. We also present a subquadratic-time algorithm that, when the graph associated with I is an expander, produces an assignment satisfying a (1- O(k^2)epsilon)-fraction of the equations. Our Cheeger inequality and first algorithm can be seen as generalisations of the Cheeger inequality and algorithm for MAX-CUT developed by Trevisan. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Huan Li and He Sun and Luca Zanetti 2019 Is Part Of LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2019.71 urn:nbn:de:0030-drops-111926 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.71 eng https://creativecommons.org/licenses/by/3.0/legalcode