scientific article; zbMATH DE number 1559517
From MaRDI portal
Publication:4526965
Recommendations
- The approximability of constraint satisfaction problems
- Approximating satisfiable satisfiability problems
- Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems
- Hard constraint satisfaction problems have hard gaps at location 1
- scientific article; zbMATH DE number 1303558
Cited in
(28)- Quantifiers and approximation
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Optimal satisfiability for propositional calculi and constraint satisfaction problems.
- Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights
- Structural properties of bounded relations with an application to NP optimization problems
- The approximability of non-Boolean satisfiability problems and restricted integer programming
- On the Hamming distance of constraint satisfaction problems.
- Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
- Independent sets with domination constraints
- Complexity and approximability of parameterized MAX-CSPs
- The approximability of constraint satisfaction problems
- Complexity and approximability of quantified and stochastic constraint satisfaction problems
- Complexity classification of local Hamiltonian problems
- Universal factor graphs for every NP-hard Boolean CSP
- Enumerating all solutions of a Boolean CSP by non-decreasing weight
- Optimization, randomized approximability, and Boolean constraint satisfaction problems
- Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems
- Strong lower bounds on the approximability of some NPO PB-complete maximization problems
- AVERAGE MEASURE, DESCRIPTIVE COMPLEXITY AND APPROXIMATION OF MAXIMIZATION PROBLEMS
- scientific article; zbMATH DE number 515727 (Why is no real title available?)
- scientific article; zbMATH DE number 6861969 (Why is no real title available?)
- From SAT to Maximum Independent Set: A New Approach to Characterize Tractable Classes
- On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE
- Some optimal inapproximability results
- Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
- The weight in enumeration
- Hard constraint satisfaction problems have hard gaps at location 1
- A dichotomy theorem for maximum generalized satisfiability problems.
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4526965)
