scientific article; zbMATH DE number 1833417

zbMATH Open0998.68028MaRDI QIDQ4780798FDOQ4780798

Authors: Lars Engebretsen 

Publication date: 21 November 2002

Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2129/21290241

Title of this publication is not available (Why is that?)

Recommendations

• The Nonapproximability of Non-Boolean Predicates
• Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness
• Approximation algorithm for non-Boolean \textsc{Max}-\(k\)-CSP
• Approximation algorithm for non-Boolean MAX \(k\)-CSP
• Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)

Mathematics Subject Classification ID

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

Cited In (11)

• Inapproximability results for equations over infinite groups
• Parity is positively useless
• The approximability of non-Boolean satisfiability problems and restricted integer programming
• A characterization of hard-to-cover CSPs
• The Complexity of Somewhat Approximation Resistant Predicates
• Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness
• The Nonapproximability of Non-Boolean Predicates
• Title not available (Why is that?)
• 3-bit dictator testing: 1 vs. 5/8
• Inapproximability results for equations over finite groups
• P ≠ NP for all infinite Boolean algebras

This page was built for publication:

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