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

DOI10.1007/S11432-013-5052-XzbMATH Open1343.68117OpenAlexW1994497972MaRDI QIDQ893727FDOQ893727

Authors: 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

Recommendations

• A general model and thresholds for random constraint satisfaction problems
• On the constraint length of random \(k\)-CSP
• Random constraint satisfaction: A more accurate picture
• New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
• Lower and Upper Bounds for Random Mimimum Satisfiability Problem

zbMATH Keywords

lower boundupper 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)

Cites Work

• Title not available (Why is that?)
• A Mathematical Theory of Communication
• Title not available (Why is that?)
• Complexity classifications of Boolean constraint satisfaction problems
• Title not available (Why is that?)
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Many hard examples in exact phase transitions
• Locating the phase transition in binary constraint satisfaction problems
• Title not available (Why is that?)
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• The scaling window of the 2-SAT transition
• Phase transitions of EXPSPACE-complete problems: a further step
• Phase transitions of EXPSPACE-complete problems
• The probabilistic analysis of a greedy satisfiability algorithm
• Random MAX SAT, random MAX CUT, and their phase transitions
• A tighter upper bound for random MAX \(2\)-SAT
• A new upper bound for 3-SAT

Cited In (6)

• Lower and Upper Bounds for Random Mimimum Satisfiability Problem
• Performances of pure random walk algorithms on constraint satisfaction problems with growing domains
• Title not available (Why is that?)
• How far from a worst solution a random solution of a \(k\) CSP instance can be?
• Phase Transition for Maximum Not-All-Equal Satisfiability
• Partition-based lower bound for Max-CSP

Uses Software

• MAX-2-SAT

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

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