DE | EN
Home
About Us
Overview
Facts and Figures
Organization
Scientists
Contact
Approach
Situations offered
Research
Overview
Application Fields
Projects
Publications
Scientists
Preprints
Institutional Cooperation
Archiv 02-14
Transfer
Overview
Industry
References
MODAL-AG
Spin Offs
Software
Patents
Schools
Overview
MathInside
Matheathlon
Matheon-Kalender
What'sMath
Training for Teachers
Summer Schools
Events
Press
Overview
Releases
News
Overview
Matheon Head
Number of the week
News 2002 - 2014
Activities
Overview
Workshops
15 Years Matheon
Media
Overview
Photos
Videos
Audios
Booklets
Books
News from around the world

Dr. Benjamin Schröter

schroeter@math.tu-berlin.de


Projects as a member

  • MI6

    Geometry of Equilibria for Shortest Path

    Prof. Dr. Michael Joswig

    Project heads: Prof. Dr. Michael Joswig
    Project members: Dr. Benjamin Schröter
    Duration: -
    Status: running
    Located at: Technische Universität Berlin

    Description

    The most basic techniques in network optimization are methods to find shortest paths between pairs of nodes in a directed graph. Classical examples include the algorithms of Dijkstra and Floyd–Warshall. These are among the core tools used, e.g., in devices which help a car driver to navigate a road network. Since efficient algorithms are available the corresponding shortest–path problems can be solved almost instantly, even on cheap hardware, and even for fairly large networks. Yet the situation for the network provider is quite different from the perspective of the network user. One reason is that the provider’s objective does not necessarily agree with the one of the user: While the individual driver might be interested in short travel times, the traffic authorities of a metropolitan city might want to, e.g., minimize the total amount of pollution. More importantly, the traffic authorities seek to achieve a system optimum, whereas the driver cares for an individual objective. Typically, in relevant cases it is next to impossible to even describe a system optimum. To help circumventing this problem, this project will focus on developing mathematical tools to assess the impact of local changes to a network a priori. Our prime application will be toward the computation of shortest paths. However, it is expected that some results can also be transferred to other network optimization problems. The optimization of networks is a central theme in combinatorial optimization. Hence the literature is abundant, and the 600 pages of the first volume of Schrijver’s monograph only form the tip of the iceberg. Modern concepts in this area include online techniques as well as robustness and randomization and dynamic algorithms. There are methods which can deal with partial or even incorrect information, and these can also be useful for analyzing modifications to a network to some extent. Further, in practice simulation plays an important role, possibly even on a microscopic level with agents modeling individual drivers. Here we propose to take a somewhat different view on this subject. We will make use of methods from polyhedral geometry to allow for addressing the relevant combinatorial optimization problems in a parameterized fashion.

    http://www3.math.tu-berlin.de/combi/dmg/2017-ECMath-MI06/

Projects as a guest