Approximation Algorithms for CSPs
From MaRDI portal
Publication:4993604
DOI10.4230/DFU.VOL7.15301.287zbMATH Open1482.68167OpenAlexW2591931678MaRDI QIDQ4993604FDOQ4993604
Authors: 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
Recommendations
- scientific article; zbMATH DE number 1002206
- Approximation algorithms for the maximum satisfiability problem
- Approximations and randomization to boost CSP techniques
- Approximating CSPs using LP relaxation
- On approximation algorithms for the minimum satisfiability problem
- The approximability of constraint satisfaction problems
- scientific article; zbMATH DE number 1264429
- scientific article; zbMATH DE number 1330032
Cites Work
- Extensions of Lipschitz mappings into a Hilbert space
- Approximate graph coloring by semidefinite programming
- The Complexity of Multiterminal Cuts
- Title not available (Why is that?)
- Title not available (Why is that?)
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Title not available (Why is that?)
- On the power of unique 2-prover 1-round games
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Simplex partitioning via exponential clocks and the multiway cut problem
- A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut
- Partitioning graphs into balanced components
- Min-max Graph Partitioning and Small Set Expansion
- Complexity of approximating CSP with balance / hard constraints
- A PCP characterization of NP with optimal amortized query complexity
- \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
- Approximation and Online Algorithms
- Graph expansion and the unique games conjecture
- Approximation resistant predicates from pairwise independence
- Approximation resistance from pairwise independent subgroups
- Beating the random ordering is hard: every ordering CSP is approximation resistant
- Towards sharp inapproximability for any 2-CSP
- Approximating unique games
- Mathematical Foundations of Computer Science 2004
- How to Play Unique Games on Expanders
- Near-optimal algorithms for unique games
- Approximation Algorithms for Graph Homomorphism Problems
- Unique games on expanding constraint graphs are easy (extended abstract)
- Multiway cut, pairwise realizable distributions, and descending thresholds
- How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games
- Near-optimal algorithms for maximum constraint satisfaction problems
- Title not available (Why is that?)
- Approximation of non-Boolean 2CSP
- Title not available (Why is that?)
- Approximation algorithm for sparsest \(k\)-partitioning
- Approximation algorithms for hypergraph small set expansion and small set vertex expansion
- Approximation algorithm for non-Boolean \textsc{Max}-\(k\)-CSP
- Improved NP-inapproximability for 2-variable linear equations
- Nonuniform graph partitioning with unrelated weights
- Near-optimal UGC-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
Cited In (17)
- Complexity of approximating CSP with balance / hard constraints
- Title not available (Why is that?)
- Every 2-CSP allows nontrivial approximation
- Title not available (Why is that?)
- Title not available (Why is that?)
- A CSP search algorithm with responsibility sets and kernels
- Title not available (Why is that?)
- Title not available (Why is that?)
- PTAS for Sparse General-valued CSPs
- Approximation algorithms for \(k\)-hurdle problems
- On approximability of satisfiable k -CSPs: I
- Towards a characterization of constant-factor approximable finite-valued CSPs
- The complexity of valued CSPs
- Recent Advances in Constraints
- Approximating Bounded Occurrence Ordering CSPs
- Robust algorithms with polynomial loss for near-unanimity CSPs
- On the complexity of CSP-based ideal membership problems
This page was built for publication: Approximation Algorithms for CSPs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993604)
