Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION.

Piotr Berman Marek Karpinski

Published in: ICALP (2002)

Keyphrases

constraint satisfaction problems
databases
np complete
information retrieval
decision making
database systems
computational complexity
approximation algorithms
phase transition