Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1999 Copyright 1999 Universität Bonn, Institut für Informatik, Abt. V
85211

Polynomial Time Approximation Schemes for Dense Instances of the Minimum Constraint Satisfaction
Cristina Bazgan, Marek Karpinski
[Download PostScript] [Download PDF]

We present a polynomial time approximation scheme for dense instances of the minimal constraint satisfaction problems, MIN kCSP. This class contains minimisation problems that search for boolean assignments to the variables minimizing the number of satisfied constraints depending on at most k variables. By dense instances of a problem in MIN kCSP we mean instances have Omega(n^(k-1))-read boolean representations where n is the number of boolean variables.

Last Change: 11/05/14 at 10:14:18
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope