research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:
TitleMultiobjective Optimization: Improved FPTAS for Shortest Paths and Non-linear Objectives with Applications
Bibtex cite IDRACTI-RU1-2009-129
Journal Theory of Computing Systems
Year published 2009
Month November
Volume 45
Number 1
Pages 162-186
DOI 10.1007/s00224-007-9096-4
Keywords Multiobjective optimization - Multiobjective shortes path - FPTAS - Non-linear objectives - Multiple constrained (optimal) path - Non-additive shortest path - Qos-aware multicommodity flow
We provide an improved FPTAS for multiobjective shortest paths—a fundamental (NP-hard) problem in multiobjective optimization—along with a new generic method for obtaining FPTAS to any multiobjective optimization problem with non-linear objectives. We show how these results can be used to obtain better approximate solutions to three related problems, multiobjective constrained [optimal] path and non-additive shortest path, that have important applications in QoS routing and in traffic optimization. We also show how to obtain a FPTAS to a natural generalization of the weighted multicommodity flow problem with elastic demands and values that models several realistic scenarios in transportation and communication networks.
Tsaggouris, George
Zaroliagis, Christos
J27-TOCS-mosp.pdf (main file)
Publication ID114