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

DOI10.1007/S11432-013-5052-XzbMath1343.68117OpenAlexW1994497972MaRDI 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 boundlower boundMax CSPMin CSPRB model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

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

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

This page was built for publication: An upper (lower) bound for Max (Min) CSP