Most optimization problems can be formulated as graph problems, where one has to find a structure (like e.g. a tour in the TSP-problem) in an underlying (capacitated) graph G=(V,E,c). Naturally, the running time that is required for solving such optimization problems crucially depends on the size of the graphs in question. One approach for quickly finding good solutions consist of not directly attacking the problem on the original graph G, but first approximating this graph by a simpler/smaller graph H that in some sense is similar to G. Hereby the similarity depends on the problem that one wants to solve.
This general paradigm has been successfully applied to a variety of different problems involving different similarity measures. In the course of this seminar we review different ways of approximating a graph, like e.g.
- approximating the cut structure of G, like e.g., mincuts, sparse cuts etc.,
- approximating distances of G with a very small graph H,
- approximating effective resistances of G,
- approximating G by a tree graph H.
The seminar will be held at a weekly date during the semester.
The seminar talks can be presented in German or English, depending on the preferences of the students.