An upper (lower) bound for Max (Min) CSP
type: Item
instance of: scholarly article
title: An upper (lower) bound for Max (Min) CSP
zbMATH Open document ID: 1343.68117
author: Ping Huang
author: Minghao Yin
publication date: 2015-11-20T00:00:00Z
full work available at URL: s11432-013-5052-x
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6512364
zbMATH Keywords: Max CSP
zbMATH Keywords: Min CSP
zbMATH Keywords: RB model
zbMATH Keywords: upper bound
zbMATH Keywords: lower bound
describes a project that uses: MAX-2-SAT
MaRDI profile type: Publication
OpenAlex ID: W1994497972
cites work: A Mathematical Theory of Communication
cites work: Complexity classifications of Boolean constraint satisfaction problems
cites work: Q4828516
cites work: Q4012216
cites work: The probabilistic analysis of a greedy satisfiability algorithm
cites work: A new upper bound for 3-SAT
cites work: Locating the phase transition in binary constraint satisfaction problems
cites work: Random constraint satisfaction: easy generation of hard (satisfiable) instances
cites work: Q4954175
cites work: The scaling window of the 2-SAT transition
cites work: Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
cites work: Q4501522
cites work: Random MAX SAT, random MAX CUT, and their phase transitions
cites work: A tighter upper bound for random MAX \(2\)-SAT
cites work: Many hard examples in exact phase transitions
cites work: PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS
cites work: Phase transitions of EXPSPACE-complete problems: a further step
DOI: 10.1007/S11432-013-5052-X
published in: Science China Information Sciences
description: scientific article; zbMATH DE number 6512364