An upper (lower) bound for Max (Min) CSP

DOI10.1007/s11432-013-5052-xzbMath1343.68117MaRDI QIDQ893727

Ping Huang, Minghao Yin

Publication date: 20 November 2015

Published in: Science China. Information Sciences (Search for Journal in Brave)

Full work available at URL: http://engine.scichina.com/doi/10.1007/s11432-013-5052-x

zbMATH Keywords

upper bound; lower bound; Max CSP; Min CSP; RB model

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Phase Transition for Maximum Not-All-Equal Satisfiability, Performances of pure random walk algorithms on constraint satisfaction problems with growing domains, Lower and Upper Bounds for Random Mimimum Satisfiability Problem

Uses Software

• MAX-2-SAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• A tighter upper bound for random MAX \(2\)-SAT
• Many hard examples in exact phase transitions
• Locating the phase transition in binary constraint satisfaction problems
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• The scaling window of the 2-SAT transition
• PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS: A FURTHER STEP
• PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS
• A new upper bound for 3-SAT
• Random MAX SAT, random MAX CUT, and their phase transitions
• The probabilistic analysis of a greedy satisfiability algorithm