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.
| 2009 |
|
|
| 2008 |
|
- 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
|
| 2008 |
|
- Hoefer, M., Souza, A., The influence of link restrictions on (random) selfish routing, 1. Symposium on Algorithmic Game Theory (SAGT), Lecture Notes in Computer Science (LNCS), Vol. 4997, pp. 22-32, 2008, Springer-Verlag.
- Hoefer, M., Competitive cost sharing with economies of scale, 8. Latin American Theoretical Informatics Conference (LATIN), Lecture Notes in Computer Science (LNCS), Vol. 4957, pp. 339-349, 2008, Springer-Verlag. abstract
- Briest, P., Hoefer, M., Krysta, P., Stackelberg network pricing games, 25. International Symposium on Theoretical Aspects of Computer Science (STACS), Springer-Verlag, pp. 133-142, 2008, Springer-Verlag. abstract
|
| 2007 |
|
- Brandes, U., Delling, D., Gaertler, M., Görke, R., Hoefer, M., Nikoloski, Z., Wagner, D., On finding graph clusterings with maximum modularity, 33. International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Lecture Notes in Computer Science (LNCS), Vol. 4769, pp. 121-132, 2007, Springer-Verlag. abstract
- Hoefer, M., Souza, A., Tradeoffs and average-case equilibria in selfish routing, 15. European Symposium on Algorithms (ESA), Lecture Notes in Computer Science (LNCS), Vol. 4698, pp. 63-74, 2007, Springer-Verlag. abstract
|
| 2006 |
|
- Brandes, U., Hoefer, M., Pich, C., Affiliation dynamics with an application to movie-actor biographies, 8. Eurographics/IEEE-VGTC Symposium on Visualization (EUROVIS), pp. 179-186, May 2006. abstract
- Brandes, U., Hoefer, M., Lerner, J., WordSpace - Visual summary of text corpora, SPIE-IS&T Electronic Imaging (VDA), SPIE, Vol. 6060, 2006. abstract
- Hoefer, M., Non-cooperative tree creation, 31. International Symposium on Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science (LNCS), Vol. 4162, pp. 517-527, 2006, Springer-Verlag. abstract
- Cardinal, J., Hoefer, M., Selfish service installation in networks, 2. International Workshop on Internet & Network Economics (WINE), Lecture Notes in Computer Science (LNCS), Vol. 4286, pp. 174-185, 2006, Springer-Verlag. abstract
- Hoefer, M., Non-cooperative facility location and covering games, 17. International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science (LNCS), Vol. 4288, pp. 369-378, 2006, Springer-Verlag. abstract
|
| 2005 |
|
- Hoefer, M., Krysta, P., Geometric network design with selfish agents, 11. International Computing and Combinatorics Conference (COCOON), Lecture Notes in Computer Science (LNCS), Vol. 3595, pp. 167-178, 2005, Springer-Verlag. abstract
|
