Background
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.
Network modifications can be very costly. The authorities can implement, e.g., speed
limits or road blocks to modify the network. However, it is often a major challenge
to understand the overall impact of such changes prior to their implementation. It is
the purpose of this project to provide the mathematical foundations for supporting
sound decisions.
In addition to their practical usefulness the Kleene stars play a fundamental role in
tropical geometry. For instance, they arise as tropical analogs of eigenspaces,
and their tropical convex hulls are convex in the ordinary sense, i.e., they
are polytropes. It is known that they form the building blocks of tropical convexity. Parametric solutions to the shortest path problem
correspond to families of polytropes. Thus,
in addition to its applicability outside of mathematics, this work is also beneficial for
inner-mathematical applications.
Goals
The key goals are:
Understanding the fibers of the map that sends a matrix to its Kleene
star in polyhedral terms, where only few of the entries in the matrix are
indeterminats.
Develop an efficient implementation for this situation.
Develop a generalization of the previous which still works in a scenario
with multiple objectives or non-cooperative agents.
