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

DOI10.1007/S11432-013-5052-XMaRDI QIDQ893727zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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
• scientific article; zbMATH DE number 6315784 (Why is no real title available?)
• 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

Describes a project that uses

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)