Flexible Network Design

Summary

Network design with its many variants is one of the most active research areas in theoretical computer science involving researchers from Algorithms and Complexity, Combinatorial Optimization, Distributed Computing and Algorithmic Game Theory. New problems in this area are arising as modern communication systems require a flexible and permanent adaptation of the network structure to highly dynamic access pattern especially in the context of mobile and adhoc networks. This brings many new aspects into network design such as flexible construction, dynamic scheduling of recources, adaptive bandwidth or spectrum assignment, and routing with respect to varying demands.

The goal of this seminar was to bring together experts from the several different communities above, and to give them the possibility to discuss recent advances, understand current trends, identify understudied areas, and formulate new directions for further investigation in this area. The seminar focussed on emergent problems in the area of flexible network design like online and oblivious network design, network design with game theoretic approaches, positioning in wireless sensor networks, and scheduling interfering signals in wireless networks.

The seminar provided an opportunity for information sharing and collaborations, and to identify new problems and areas for future collaboration. Indeed, to facilitate the exchange of ideas, some of the participants were requested to give overview talks or surveys of subjects of cross-cutting interest; this was complemented by shorter talks by other participants on specific research results.