Choosing a heaviest subgraph greedily {Register ASAP at http://www.mpi-sb.mpg.de/units/ag3/talks.html}

given a graph $G=(V,E)$ with positive weights on its edges,
and an integer $k$, choose a subset $U$ of $k$ nodes,
such that the weight of the subgraph induced by $U$ is maximal.

We present various methods for finding an approximate solution
for this problem. This methods include the use of greedy methods,
linear programming and randomized-rounding methods, and convex
(semi-definite)
programming methods that resemble and extend the Goemans-Williamson method
for the Max-Cut problem.