The relaxation can be extended by assigning to each node not just a unit scalar (-1 or 1) but a unit length vector in a space of dimension m £ n. In this case the association of a node i to a set S cannot be done directly. This will be done later using a random technique.
