Result: An FPTAS for quickest multicommodity flows with inflow-dependent transit times

Title:
An FPTAS for quickest multicommodity flows with inflow-dependent transit times
Authors:
HALL, Alex, LANGKAU, Katharina, SKUTELLA, Martin
Source:
An APPOL meeting in Bertinoro, Italy, 23-28 March 2003Algorithmica. 47(3):299-321
Publisher Information:
New York, NY: Springer, 2007.
Publication Year:
2007
Physical Description:
print, 24 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Logiciel, Software, Systèmes informatiques et systèmes répartis. Interface utilisateur, Computer systems and distributed systems. User interface, Transports terrestres, transports aeriens, transports maritimes, constructions navales, Ground, air and sea transportation, marine construction, Transports et trafic routiers, Road transportation and traffic, Approximation polynomiale, Polynomial approximation, Aproximación polinomial, Dépendance du temps, Time dependence, Dependencia del tiempo, Flot réseau, Network flow, Flujo red, Modélisation, Modeling, Modelización, Problème NP difficile, NP hard problem, Problema NP duro, Problème multiflot, Multicommodity flow problem, Problema multiflujo, Routage, Routing, Enrutamiento, Réseau communication, Communication network, Red de comunicación, Réseau routier, Road network, Red carretera, Système production, Production system, Sistema producción, Temps parcours, Transit time, Tiempo recorrido, Temps polynomial, Polynomial time, Tiempo polinomial, Trafic routier, Road traffic, Tráfico carretera, Approximation, Network flows over time, Transit times
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Institut für Theoretische Informatik, ETH Zentrum, CAB H 39.2, 8092 Zürich, Switzerland
Institut für Mathematik, TU Berlin, Straße des 17 Juni 136, 10623 Berlin, Germany
Fachbereich Mathematik, Universität Dortmund, 44221 Dortmund, Germany
ISSN:
0178-4617
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=18660761
Rights:
Copyright 2007 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Building. Public works. Transport. Civil engineering

Computer science; theoretical automation; systems
Accession Number:
edscal.18660761
Database:
PASCAL Archive

Further Information

Given a network with capacities and transit times on the arcs, the quickest flow problem asks for a flow over time that satisfies given demands within minimal time. In the setting of flows over time, flow on arcs may vary over time and the transit time of an arc is the time it takes for flow to travel through this arc. In most real-world applications (such as, e.g., road traffic, communication networks, production systems, etc.), transit times are not fixed but depend on the current flow situation in the network. We consider the model where the transit time of an arc is given as a non-decreasing function of the rate of inflow into the arc. We prove that the quickest s-t-flow problem is NP-hard in this setting and give various approximation results, including a fully polynomial time approximation scheme (FPTAS) for the quickest multicommodity flow problem with bounded cost.