Approximation Algorithms for CSPs
From MaRDI portal
Publication:4993604
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
- scientific article; zbMATH DE number 5485510 (Why is no real title available?)
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 1775387 (Why is no real title available?)
- scientific article; zbMATH DE number 2086914 (Why is no real title available?)
- scientific article; zbMATH DE number 6783493 (Why is no real title available?)
- A PCP characterization of NP with optimal amortized query complexity
- A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut
- Approximate graph coloring by semidefinite programming
- Approximating unique games
- Approximation Algorithms for Graph Homomorphism Problems
- Approximation algorithm for non-Boolean \textsc{Max}-\(k\)-CSP
- Approximation algorithm for sparsest \(k\)-partitioning
- Approximation algorithms for hypergraph small set expansion and small set vertex expansion
- Approximation and Online Algorithms
- Approximation of non-Boolean 2CSP
- Approximation resistance from pairwise independent subgroups
- Approximation resistant predicates from pairwise independence
- Beating the random ordering is hard: every ordering CSP is approximation resistant
- Complexity of approximating CSP with balance / hard constraints
- Extensions of Lipschitz mappings into a Hilbert space
- Graph expansion and the unique games conjecture
- How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games
- How to Play Unique Games on Expanders
- Improved NP-inapproximability for 2-variable linear equations
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Mathematical Foundations of Computer Science 2004
- Min-max Graph Partitioning and Small Set Expansion
- Multiway cut, pairwise realizable distributions, and descending thresholds
- Near-optimal UGC-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
- Near-optimal algorithms for maximum constraint satisfaction problems
- Near-optimal algorithms for unique games
- Nonuniform graph partitioning with unrelated weights
- On the power of unique 2-prover 1-round games
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Partitioning graphs into balanced components
- Simplex partitioning via exponential clocks and the multiway cut problem
- Some optimal inapproximability results
- The Complexity of Multiterminal Cuts
- Towards sharp inapproximability for any 2-CSP
- Unique games on expanding constraint graphs are easy (extended abstract)
- \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
Cited in
(17)- Complexity of approximating CSP with balance / hard constraints
- scientific article; zbMATH DE number 7651202 (Why is no real title available?)
- Every 2-CSP allows nontrivial approximation
- scientific article; zbMATH DE number 7561584 (Why is no real title available?)
- scientific article; zbMATH DE number 7716602 (Why is no real title available?)
- A CSP search algorithm with responsibility sets and kernels
- scientific article; zbMATH DE number 7758361 (Why is no real title available?)
- scientific article; zbMATH DE number 6381654 (Why is no real title available?)
- PTAS for Sparse General-valued CSPs
- Approximation algorithms for \(k\)-hurdle problems
- Towards a characterization of constant-factor approximable finite-valued CSPs
- On approximability of satisfiable k -CSPs: I
- 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)
