Approximability of the Maximum Solution Problem for Certain Families of Algebras

DOI10.1007/978-3-642-03351-3_21zbMATH Open1223.68041OpenAlexW1524072139MaRDI QIDQ3392956FDOQ3392956

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

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

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)

Cites Work

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

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)