An upper (lower) bound for Max (Min) CSP
From MaRDI portal
Publication:893727
DOI10.1007/s11432-013-5052-xzbMath1343.68117MaRDI QIDQ893727
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
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
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