Approximating unique games using low diameter graph decomposition

DOI10.4230/LIPICS.APPROX-RANDOM.2017.18MaRDI QIDQ5002621zbMATH OpenOpenAlexFDO

Authors Vedat Levi Alev, Lap Chi Lau

Publication date 28 July 2021

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

zbMATH Keywords

approximation algorithmsbounded-genus graphsfixed minor-free graphslinear programminglow-diameter graph decompositionunique games

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Abstract: We design approximation algorithms for Unique Games when the constraint graph admits good low diameter graph decomposition. For the ${sfMax2Lin}_k$ problem in $K_r$-minor free graphs, when there is an assignment satisfying $1-varepsilon$ fraction of constraints, we present an algorithm that produces an assignment satisfying $1-O(rvarepsilon)$ fraction of constraints, with the approximation ratio independent of the alphabet size. A corollary is an improved approximation algorithm for the $sfMaxCut$ problem for $K_r$-minor free graphs. For general Unique Games in $K_r$-minor free graphs, we provide another algorithm that produces an assignment satisfying $1-O(rsqrtvarepsilon)$ fraction of constraints. Our approach is to round a linear programming relaxation to find a minimum subset of edges that intersects all the inconsistent cycles. We show that it is possible to apply the low diameter graph decomposition technique on the constraint graph directly, rather than to work on the label extended graph as in previous algorithms for Unique Games. The same approach applies when the constraint graph is of genus $g$, and we get similar results with $r$ replaced by $logg$ in the ${sfMax2Lin}_k$ problem and by $sqrtlogg$ in the general problem. The former result generalizes the result of Gupta-Talwar for Unique Games in the ${sfMax2Lin}_k$ case, and the latter result generalizes the result of Trevisan for general Unique Games.

Recommendations

• Subexponential algorithms for unique games and related problems
• Near-optimal algorithms for unique games
• Approximation algorithms for unique games
• Spectral algorithms for unique games
• Graph expansion and the unique games conjecture

Cites work

• \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
• A tight bound on approximating arbitrary metrics by tree metrics
• Approximating unique games
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation algorithms for unique games
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Compositions in the bipartite subgraph polytope
• Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
• Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
• Excluded minors, network decomposition, and multicommodity flow
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Geometric algorithms and combinatorial optimization
• Graph expansion and the unique games conjecture
• How to Play Unique Games on Expanders
• scientific article; zbMATH DE number 5485536 (Why is no real title available?)
• scientific article; zbMATH DE number 6297701 (Why is no real title available?)
• Iterative methods in combinatorial optimization.
• Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
• Linearity of grid minors in treewidth with applications through bidimensionality
• Metric uniformization and spectral bounds for graphs
• Min-max Graph Partitioning and Small Set Expansion
• Near-optimal algorithms for unique games
• On the power of unique 2-prover 1-round games
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Rounding Semidefinite Programming Hierarchies via Global Correlation
• Spectral algorithms for unique games
• Spectral partitioning works: planar graphs and finite element meshes
• Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus
• Subexponential algorithms for unique games and related problems
• Unique games on expanding constraint graphs are easy (extended abstract)
• Unique games on the hypercube
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(4)

• On Khot’s unique games conjecture
• Subexponential algorithms for unique games and related problems
• Graph Clustering using Effective Resistance
• scientific article; zbMATH DE number 7650073 (Why is no real title available?)

This page was built for publication: Approximating unique games using low diameter graph decomposition

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