# Events

## Talk given by Dr. Martin Gairing (University of Liverpool)

Begin: Tue, 03. of Sep 2013 ( 3:00 PM)Location: Fürstenallee 11, Room F1.110

On September 3, 2013, Dr. Martin Gairing will give a talk on "Complexity and Approximation of the Continuous Network Design Problem".

Abstract:

We revisit a classical problem in transportation, known as the
continuous (bilevel) network design problem, CNDP for short. We are
given a graph for which the latency of each edge depends on the ratio of
the edge flow and the capacity installed. The goal is to find an optimal
investment in edge capacities so as to minimize the sum of the routing
cost of the induced Wardrop equilibrium and the investment cost. While
this problem is considered as challenging in the literature, its
complexity status was still unknown. We close this gap showing that CNDP
is strongly NP-complete and APX-hard, even for instances with affine
latencies.

As for the approximation of the problem, we first provide a detailed
analysis for a heuristic studied by Marcotte for the special case of
monomial latency functions (Mathematical Programming, Vol. 34, 1986).
Specifically, we derive a closed form expression of its approximation
guarantee for arbitrary sets of allowed latency functions. Second, we
propose a different approximation algorithm and show that it has the
same approximation guarantee. As our final -- and arguably most
interesting -- result regarding approximation, we show that using the
better of the two approximation algorithms results in a strictly
improved approximation guarantee for which we give a closed form
expression. For affine latencies, e.g., this algorithm achieves a
49/41-approximation which improves on the 5/4 that has been shown before
by Marcotte.

Joint work with Tobias Harks and Max Klimm.