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.