  Given a graph G = (V,E) and a parameter k, we consider the problem of finding
a subset U in V of size k that maximizes the number of induced edges (DkS). We
improve upon the previously best known approximation ratio for DkS, a ratio
that has not seen any progress during the last decade. Specifically, we improve
the approximation ratio from n^{0.32258} to n^{0.3159}.
  The improved ratio is obtained by studying a variant to the DkS problem in
which one considers the problem of finding a subset U in V of size at most k
that maximizes the number of induced edges.
  Finally, we study the DkS variant in which one considers the problem of
finding a subset U in V of size at least k that maximizes the number of induced
edges.
