Approximability of the Maximum Solution Problem for Certain Families of Algebras

DOI10.1007/978-3-642-03351-3_21zbMath1223.68041OpenAlexW1524072139MaRDI QIDQ3392956

Johan Thapper, Peter Jonsson

Publication date: 18 August 2009

Published in: Computer Science - Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03351-3_21

zbMATH Keywords

computational complexityoptimisationconstraint satisfactionalgebraapproximability

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

The Complexity of Valued CSPs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the algebraic structure of combinatorial problems
• Combinatorial problems raised from 2-semilattices
• The Approximability of Constraint Satisfaction Problems
• The Maximum Solution Problem on Graphs
• MAX ONES Generalized to Larger Domains
• Closure properties of constraints
• Classifying the Complexity of Constraints Using Finite Algebras
• Mathematical Foundations of Computer Science 2005
• On the Foundations of Combinatorial Theory IV Finite Vector Spaces and Eulerian Generating Functions
• Generalised Integer Programming Based on Logically Defined Relations

This page was built for publication: Approximability of the Maximum Solution Problem for Certain Families of Algebras