In this seminar, Tim Oo sterwijk will give a talk about Bicriteria Nash Flows over Time.
Flows over time are a natural way to incorporate flow dynamics tha t arise in various applications such as traffic networks. In this tal k we introduce a natural variant of the deterministic fluid queuing m odel in which users aim to minimize their costs subject to arrival at their destination before a pre-specified deadline. We determine the existence and the structure of Nash flows over time and fully charact erize the price of anarchy for this model. The price of anarchy measu res the ratio of the quality of the equilibrium and the quality of th e optimum flow, where we evaluate the quality using two different nat ural performance measures: the throughput for a given deadline and th e makespan for a given amount of flow. While it turns out that both p rices of anarchy can be unbounded in general, we provide tight bounds for the important subclass of parallel path graphs.
DESCRIPTION: Flows over time are a natural way to incorporate flow dyn amics that arise in various applications such as traffic networks. In this talk we introduce a natural variant of the deterministic fluid queuing model in which users aim to minimize their costs subject to a rrival at their destination before a pre-specified deadline. We deter mine the existence and the structure of Nash flows over time and full y characterize the price of anarchy for this model. The price of anar chy measures the ratio of the quality of the equilibrium and the qual ity of the optimum flow, where we evaluate the quality using two diff erent natural performance measures: the throughput for a given deadli ne and the makespan for a given amount of flow. While it turns out th at both prices of anarchy can be unbounded in general, we provide tig ht bounds for the important subclass of parallel path graphs. In this seminar, Tim Oosterwijk will give a talk about Bicriteria Nash Flows over Time. END:VEVENT END:VCALENDAR