Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

**Date and Time**: Tuesday, February 17, 2004, 12:15 pm

**Duration**: This information is not available in the database

**Location**: This information is not available in the database

**Speaker**: Alexander Hall

Flow variation over time is an important feature in network flow
problems arising in various applications such as road or air traffic
control, production systems, communication networks (e.g., the
Internet), and financial flows. The common characteristic are
networks with capacities and transit times on the edges which specify
the amount of time it takes for flow to travel through a particular
edge. Moreover, in contrast to static flow problems, flow values on
edges may change with time in these networks.

I will give a short introduction to the flows over time problem and
mention new complexity and inapproximability results for the case
where the transit times are assumed to be constant.

In many real-world applications transit times are not constant but
depend on the current flow situation in the network. For the model
where the transit time of an edge is given as a nondecreasing function
of the rate of inflow into the edge I will present the ideas
underlying an FPTAS for the `quickest multicommodity flow problem with
bounded cost'. It can be shown that this problem is NP-hard even in
the single commodity case.

This is joint work with Steffen Hippler, Katharina Langkau, and Martin Skutella.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login