Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights

DOI10.1016/S0304-3975(98)00343-0zbMath0945.68078MaRDI QIDQ1575713

Peter Jonsson

Publication date: 21 August 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

computational complexityoptimization problemsBoolean constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (5)

Supermodular functions and the complexity of MAX CSP ⋮ Universal qudit Hamiltonians ⋮ Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights ⋮ Complexity Classification of Local Hamiltonian Problems ⋮ Introduction to the Maximum Solution Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A dichotomy theorem for maximum generalized satisfiability problems.
• On the complexity of H-coloring
• The directed subgraph homeomorphism problem
• A bounded approximation for the minimum cost 2-sat problem
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• Complexity of generalized satisfiability counting problems
• The complexity of satisfiability problems

This page was built for publication: Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights