Approximability of Bounded Occurrence Max Ones

DOI10.1007/11821069_54MaRDI QIDQ5756725zbMATH OpenOpenAlexFDO

Authors Fredrik Kuivinen

Publication date 5 September 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11821069_54

zbMATH Keywords

ApproximabilityBounded occurrenceConstraint satisfaction problemsMatchingMax Ones

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• MAX ONES Generalized to Larger Domains
• The approximability of constraint satisfaction problems
• The approximability of MAX CSP with fixed-value constraints
• Non-approximability results for optimization problems on bounded degree instances
• Approximability of clausal constraints

Cited in

(1)

• Upper bounds on the running time of the univariate marginal distribution algorithm on OneMax

This page was built for publication: Approximability of Bounded Occurrence Max Ones

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