Approximability of the Maximum Solution Problem for Certain Families of Algebras

DOI10.1007/978-3-642-03351-3_21MaRDI QIDQ3392956zbMATH OpenOpenAlexFDO

Authors Peter Jonsson, Johan Thapper

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)

Recommendations

• Approximability of Integer Programming with Generalised Constraints
• Introduction to the Maximum Solution Problem
• MAX ONES Generalized to Larger Domains
• Approximability of clausal constraints
• The approximability of MAX CSP with fixed-value constraints

Cites work

• scientific article; zbMATH DE number 4150250 (Why is no real title available?)
• scientific article; zbMATH DE number 3972929 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Combinatorial problems raised from 2-semilattices
• Generalised Integer Programming Based on Logically Defined Relations
• MAX ONES Generalized to Larger Domains
• Mathematical Foundations of Computer Science 2005
• On the Foundations of Combinatorial Theory IV Finite Vector Spaces and Eulerian Generating Functions
• On the algebraic structure of combinatorial problems
• The Maximum Solution Problem on Graphs
• The approximability of constraint satisfaction problems

Cited in

(5)

• Mathematical Foundations of Computer Science 2005
• Approximability of Integer Programming with Generalised Constraints
• An improved algorithm for finding the generators of the solution space for \(A\otimes \mathbf{x}\ge \mathbf{x} \)
• MAX ONES Generalized to Larger Domains
• The complexity of valued CSPs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3392956)