Approximation algorithms for MAX-CUT, when sizes of partition sets are fixed The MAX-CUT problem has constant factor approximation, but we can't control the sizes of the sets in resulting partition. What is known about maximizing cut size, if we restrict one part of the partition to have size exactly $k$?

Formally, given a graph $G(V, E)$ and integer $k$, find the set $S \subset V$, such that $|S| = k$ and the number of edges between $S$ and $V \setminus S$ is maximized. What is the name of this problem (for example, if $k = |V|/2$, this is known as MAX-BISECTION)? Does it become easier to approximate in polynomial time, if $k$ is $polylog(|V|)$?
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.