Approximation algorithms for MAX-CUT, when sizes of partition sets are fixed
There is a 1/2-approximation for Max-Cut with a given size k where k is part of the input. This is in a paper of Ageev and Sviridenko on pipage rounding. See below.
http://www.springerlink.com/content/r37k4302n7m17427/

The above problem is an example of submodular function maximization subject to a matroid base constraint. There has been much recent work on submodular function maximization subject to a variety of constraints.