Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem

DOI10.4230/LIPICS.ESA.2019.71OpenAlexW2979088439MaRDI QIDQ5075818FDOQ5075818

Authors: He Sun, Luca Zanetti, Hu-An Li 

Publication date: 11 May 2022

Full work available at URL: https://arxiv.org/abs/1811.10909

Recommendations

• Max cut and the smallest eigenvalue
• Max CUT and the smallest eigenvalue
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• Many sparse cuts via higher eigenvalues

zbMATH Keywords

spectral methodsunique gamesHermitian Laplaciansthe Max-2-Lin problem

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Title not available (Why is that?)
• Eigenvalues and expanders
• Reducibility among combinatorial problems
• Authoritative sources in a hyperlinked environment
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Graph sparsification by effective resistances
• On the power of unique 2-prover 1-round games
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Max cut and the smallest eigenvalue
• A Cheeger Inequality for the Graph Connection Laplacian
• Improved Cheeger's inequality, analysis of spectral partitioning algorithms through higher order spectral gap
• Angular synchronization by eigenvectors and semidefinite programming
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• Approximating unique games
• Subexponential algorithms for unique games and related problems
• Near-optimal algorithms for unique games
• Unique games on expanding constraint graphs are easy (extended abstract)
• Spectral algorithms for unique games
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• A new way of using semidefinite programming with applications to linear equations mod \(p\)
• Fast SDP algorithms for constraint satisfaction problems
• Partitioning well-clustered graphs: spectral clustering works!

Cited In (1)

• A Look at the Generalized Heron Problem through the Lens of Majorization-Minimization

This page was built for publication: Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5075818)