• search hit 345 of 1103
Back to Result List

Extreme Point Characterization for Continuous-time Dynamic Shortest Path Problems with Arbitrary Transit Times

Please always quote using this URN:urn:nbn:de:0296-matheon-8129
  • We consider the dynamic shortest path problem in the continuous-time model because of its importance. This problem has been extensively studied in the literature. But so far, all contributions to this problem are based on the assumption that all transit times are strictly positive. However, in order to study dynamic network flows it is essential to support negative transit times since they occur quite naturally in residual networks. In this paper we extend the work of Philpott [SIAM Control Opt.,~1994, pp.~538--552] to the case of arbitrary (also negative and irrational) transit times. We study a corresponding linear program in a space of measures and give a full characterization of its extreme points. In particular, we show a one-to-one correspondence between extreme points and dynamic paths.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Ronald Koch, Ebrahim Nasrabadi
URN:urn:nbn:de:0296-matheon-8129
Referee:Martin Skutella
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2011/04/26
Release Date:2011/04/26
Tag:
Institute:Research Center Matheon
Technische Universität Berlin
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C21 Flows in graphs
28-XX MEASURE AND INTEGRATION (For analysis on manifolds, see 58-XX) / 28Axx Classical measure theory / 28A25 Integration with respect to measures and other set functions
49-XX CALCULUS OF VARIATIONS AND OPTIMAL CONTROL; OPTIMIZATION [See also 34H05, 34K35, 65Kxx, 90Cxx, 93-XX] / 49Jxx Existence theories / 49J27 Problems in abstract spaces [See also 90C48, 93C25]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C48 Programming in abstract spaces
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C49 Extreme-point and pivoting methods
Preprint Number:779
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.