Approximation of Constraint Satisfaction via local search

DOI10.1007/3-540-60220-8_85zbMath1502.68275OpenAlexW2284007041MaRDI QIDQ5057457

Hoong Chuin Lau

Publication date: 16 December 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-60220-8_85

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Dynamic algorithms for classes of constraint satisfaction problems

Cites Work

• Network-based heuristics for constraint-satisfaction problems
• How well can a graph be n-colored?
• On the complexity of approximating the independent set problem
• Optimization, approximation, and complexity classes
• A bound on the chromatic number of a graph
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• Simple Local Search Problems that are Hard to Solve
• A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
• On Syntactic versus Computational Views of Approximability
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item