2026-07-20T05:06:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:682 2024-03-06T10:28:25Z ddc:004 open_access

QoS-aware Multicommodity Flows and Transportation Planning Tsaggouris, George Zaroliagis, Christos Quality of service multicommodity flows fully polynomial approximation scheme transportation planning We consider the emph{QoS-aware Multicommodity Flow} problem, a natural generalization of the weighted multicommodity flow problem where the demands and commodity values are elastic to the Quality-of-Service characteristics of the underlying network. The problem is fundamental in transportation planning and also has important applications beyond the transportation domain. We provide a FPTAS for the QoS-aware Multicommodity Flow problem by building upon a Lagrangian relaxation method and a recent FPTAS for the non-additive shortest path problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik George Tsaggouris and Christos Zaroliagis 2006 Is Part Of OASIcs, Volume 5, 6th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'06) (2006) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2006.682 urn:nbn:de:0030-drops-6827 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2006.682 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode