University of Konstanz
Graduiertenkolleg / PhD Program
Computer and Information Science

Martin Hoefer

Doctoral Student in the PhD program from 01.10.2004 to 30.09.2007.
Currently PostDoc at RWTH Aachen, Lehrstuhl für Informatik 1: Algorithmen und Komplexität. Homepage.


1. Prof. Dr. Ulrik Brandes
2. Prof. Dr. Dietmar Saupe

organisational data

Room: E 215
Tel.: +49 (0)7531 / 88-4263
E-mail: hoefer "at"
Other Resources:

project description

Clustering and optimization under distributed competition

Combinatorial optimization problems have long been studied in the area of efficient algorithms. The emergence of the internet and the ever-growing size of the instances poses new distributed and competitive approaches. They must capture the economic and selfish nature of independent agents that build, maintain and operate the internet. The consideration of these aspects poses new questions about cooperation and coordination of distributed rational agents. Under which conditions are they motivated to contribute towards a globally efficient feasible solution? How efficient is a solution that independent agents can agree upon? How hard is it to calculate such stable outcomes?

Mathematically rigorous treatments of questions like these involve standard algorithmic techniques in combination with notions from game theory. The thesis will focus on characterizations of efficiency and stability and their trade-offs in distributed competitive variants of network design and combinatorial optimization problems. These variants serve to capture fundamental aspects of the development of the internet and e-commerce. Furthermore, game-theoretic models in graph-theoretic optimization, clustering and facility location are studied. They are used to model problems arising in distributed network design, data analysis and the development of social networks.


The following list of publications covers only those, which are or were published during participation at the Graduiertenkolleg / PhD program.

Articles in Journals

  • Brandes, U., Delling, D., Gaertler, M., Görke, R., Hoefer, M., Nikoloski, Z., Wagner, D., On modularity clustering, IEEE Transactions on Knowledge and Data Engineering, Vol. 20, No. 2, pp. 172-188, 2008. abstract

Conference Papers


Technical Reports


Phd Theses


curriculum vitae

1998 - 2004 Studies of Computer Science at the TU Clausthal, Germany
Degree : Graduate Engineer. 
2002 Summer intern at the AG1 group of Kurt Mehlhorn, Max-Planck-Institut für Informatik, Saarbrücken, Germany.
2000 - 2001 PhD-Student in Operations Research at the University of Colorado in Boulder, USA.
1991 - 1998 Highschool in Osterode, Germany.