MAX ONES Generalized to Larger Domains

DOI10.1137/060669231zbMath1162.68015OpenAlexW2076265075MaRDI QIDQ3614161

Fredrik Kuivinen, Peter Jonsson, 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

combinatorial optimizationcloneconstraint satisfactionapproximability

Mathematics Subject Classification ID

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

Related Items (8)

Necessary Conditions for Tractability of Valued CSPs ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ PTAS for Sparse General-valued CSPs ⋮ The Complexity of Valued CSPs ⋮ Approximability of clausal constraints ⋮ Approximability of the Maximum Solution Problem for Certain Families of Algebras ⋮ Peek arc consistency ⋮ Introduction to the Maximum Solution Problem

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