Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1999 Copyright 1999 University of Bonn, Department of Computer Science, 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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V