scientific article; zbMATH DE number 2019637

MaRDI QIDQ4440440zbMATH OpenFDO

Authors Lars Engebretsen, Venkatesan Guruswami

Publication date 17 December 2003

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2483/24830224.htm

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Is constraint satisfaction over two variables always easy?
• Why almost all satisfiable k-CNF formulas are easy
• Constraint satisfaction problems: convexity makes AllDifferent constraints tractable
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Sparsification of two-variable valued constraint satisfaction problems
• Constraint Satisfaction
• scientific article; zbMATH DE number 1008453
• Artificial Intelligence: Methodology, Systems, and Applications
• A new algorithm for optimal 2-constraint satisfaction and its implications

Cited in

(10)

• Universal factor graphs
• Complexity of approximating CSP with balance/hard constraints
• Is constraint satisfaction over two variables always easy?
• On the NP-hardness of Max-Not-2
• ETH-hardness of approximating 2-CSPs and directed Steiner network
• Towards a characterization of approximation resistance for symmetric CSPs
• (2+)-Sat is NP-hard
• Towards a characterization of approximation resistance for symmetric CSPs
• On the NP-hardness of MAX-Not-2
• Every 2-CSP allows nontrivial approximation

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 Q4440440)