Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights
From MaRDI portal
Recommendations
- Principles and Practice of Constraint Programming – CP 2004
- Optimization, randomized approximability, and Boolean constraint satisfaction problems
- The Complexity of Weighted Boolean #CSP
- Algorithms and Computation
- Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
Cites work
- scientific article; zbMATH DE number 3644821 (Why is no real title available?)
- scientific article; zbMATH DE number 3121293 (Why is no real title available?)
- scientific article; zbMATH DE number 3121294 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 1559517 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- scientific article; zbMATH DE number 751135 (Why is no real title available?)
- A bounded approximation for the minimum cost 2-sat problem
- A dichotomy theorem for maximum generalized satisfiability problems.
- Complexity of generalized satisfiability counting problems
- On the complexity of H-coloring
- The complexity of satisfiability problems
- The directed subgraph homeomorphism problem
- Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
Cited in
(18)- Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
- On the Hardness of Losing Weight
- scientific article; zbMATH DE number 5263038 (Why is no real title available?)
- scientific article; zbMATH DE number 7204481 (Why is no real title available?)
- Introduction to the Maximum Solution Problem
- Boolean query optimization and the 0-1 hyperbolic sum problem
- Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
- scientific article; zbMATH DE number 6861969 (Why is no real title available?)
- Complexity classification of local Hamiltonian problems
- New heuristics and adaptive memory procedures for Boolean optimization problems
- On the hardness of losing weight
- Universal qudit Hamiltonians
- Improving Unsatisfiability-Based Algorithms for Boolean Optimization
- Principles and Practice of Constraint Programming – CP 2004
- Supermodular functions and the complexity of MAX CSP
- Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
- Optimization, randomized approximability, and Boolean constraint satisfaction problems
- Weighted NP Optimization Problems: Logical Definability and Approximation Properties
This page was built for publication: Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1575713)
