MAX ONES Generalized to Larger Domains

DOI10.1137/060669231MaRDI QIDQ3614161zbMATH OpenOpenAlexFDO

Authors Peter Jonsson, Fredrik Kuivinen, Gustav Nordh

Publication date 16 March 2009

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/060669231

zbMATH Keywords

approximabilityclonecombinatorial optimizationconstraint satisfaction

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Approximability of Integer Programming with Generalised Constraints
• Approximability of clausal constraints
• Approximability of the Maximum Solution Problem for Certain Families of Algebras
• Introduction to the Maximum Solution Problem
• The approximability of constraint satisfaction problems

Cited in

(10)

• Peek arc consistency
• Approximability of the Maximum Solution Problem for Certain Families of Algebras
• Necessary conditions for tractability of valued CSPs
• Approximability of Integer Programming with Generalised Constraints
• The complexity of valued CSPs
• The power of Sherali-Adams relaxations for general-valued CSPs
• Introduction to the Maximum Solution Problem
• Approximability of Bounded Occurrence Max Ones
• PTAS for Sparse General-valued CSPs
• Approximability of clausal constraints

This page was built for publication: MAX ONES Generalized to Larger Domains

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