Approximation of Constraint Satisfaction via local search

DOI10.1007/3-540-60220-8_85MaRDI QIDQ5057457zbMATH OpenOpenAlexFDO

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

Cites work

• .878-approximation algorithms for MAX CUT and MAX 2SAT
• A bound on the chromatic number of a graph
• A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
• How well can a graph be n-colored?
• scientific article; zbMATH DE number 910871 (Why is no real title available?)
• scientific article; zbMATH DE number 1414323 (Why is no real title available?)
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Network-based heuristics for constraint-satisfaction problems
• On Syntactic versus Computational Views of Approximability
• On the complexity of approximating the independent set problem
• Optimization, approximation, and complexity classes
• Simple Local Search Problems that are Hard to Solve

Cited in

(1)

• Dynamic algorithms for classes of constraint satisfaction problems

This page was built for publication: Approximation of Constraint Satisfaction via local search

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