In situations in which it is hard to compute optimal solutions exactly, one may resort to techniques that are close to optimal. More concretely, for the class of NP-complete problems, which are generally believed to be non-solvable in polynomial time, one could try to develop techniques that yield a solution that is at most a fixed percentage off the optimal value. A commonly applied and powerful approximation idea is to first consider a convex relaxation of the problem at hand, and then convert this into an integral solution. One major challenge lies in determining the class of network problems for which such relaxations work, also relying on the concept of convex programming hierarchies.
A second topic concerns techniques that focus on average case behavior of algorithms, rather than on worst-case behavior. A key question in this respect is which structural properties of real-world networks facilitate the development of algorithms that are fast for ``most” instances.
The projects related to this theme are: