Despite decades of effort, the algorithmic complexity of the simplex algorithm for linear programming remains unsettled. One of the questions one is led to ask in this context is the following: What is the largest number of vertices on an ascending path along the edges of a d-dimensional polytope? (Here ascending is meant with respect to some linear objective function.) This corresponds to the worst-case behaviour of the simplex algorithm on the set of all possible pivot strategies.

One possible answer is suggested by McMullen's Upper Bound Theorem, which tells us the maximal number of vertices that any n-facet d-polytope can have. In this talk, we will show that at least in dimension 4 this bound is actually sharp, by exhibiting a family of simple 4-polytopes with maximal possible number of vertices that admit an ascending path passing through all of them.

Motivated by applications in road traffic control, we study flows in networks featuring special characteristics. Firstly, there are transit times on the arcs of the network which specify the amount of time it takes for flow to travel through an arc; in particular, flow values on arcs may change over time. Secondly, the transit time of an arc varies with the current amount of flow using this arc.

Most problems dealing with flows over time and constant transit times can be translated to static flow problems in time-expanded networks. Using similar ideas, we develop an alternative time-expanded network with flow-dependent transit times to which the whole algorithmic toolbox developed for static flows can be applied. Although this approach does not entirely capture the behavior of flows over time with flow-dependent transit times, we present approximation results which provide evidence of its surprising quality.

Dominance constraints are logical descriptions of trees that have numerous applications in computational linguistics. Efficient algorithms for the subclass of normal dominance constraints were proposed by Mehlhorn at al recently. We present a new graph algorithm that enumerates the solved forms of weakly normal dominance constraints. We thereby improve on the best previously known algorithm for normal dominance constraints in efficiency, coverage, and applicability.