Approximation Algorithms for CSPs
From MaRDI portal
Publication:4993604
DOI10.4230/DFU.Vol7.15301.287zbMath1482.68167OpenAlexW2591931678MaRDI QIDQ4993604
Konstantin Makarychev, Yury Makarychev
Publication date: 15 June 2021
Full work available at URL: https://dblp.uni-trier.de/db/conf/dagstuhl/dfu7.html#MakarychevM17
Related Items (8)
Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ PTAS for Sparse General-valued CSPs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Complexity of Valued CSPs ⋮ Unnamed Item ⋮ Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut
- Approximation resistant predicates from pairwise independence
- Rounding algorithms for a geometric embedding of minimum multiway cut
- Graph expansion and the unique games conjecture
- Near-optimal algorithms for unique games
- Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion
- Complexity of approximating CSP with balance / hard constraints
- Towards Sharp Inapproximability for Any 2-CSP
- How to Play Unique Games on Expanders
- Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant
- A PCP characterization of NP with optimal amortized query complexity
- Extensions of Lipschitz mappings into a Hilbert space
- On the power of unique 2-prover 1-round games
- O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
- Approximating unique games
- Approximation Algorithms for Graph Homomorphism Problems
- Approximate graph coloring by semidefinite programming
- The Complexity of Multiterminal Cuts
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Approximation of non-boolean 2CSP
- Near-Optimal UGC-hardness of Approximating Max k-CSP_R
- Nonuniform Graph Partitioning with Unrelated Weights
- Multiway cut, pairwise realizable distributions, and descending thresholds
- Mathematical Foundations of Computer Science 2004
- Approximation Algorithm for Sparsest k-Partitioning
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games
- Min-max Graph Partitioning and Small Set Expansion
- Approximation resistance from pairwise independent subgroups
- Simplex partitioning via exponential clocks and the multiway cut problem
- Approximation and Online Algorithms
This page was built for publication: Approximation Algorithms for CSPs
