Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-Linear Objectives with Applications
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.
multiobjective optimization fptas non-linear objectives non-additive shortest path multiobjective shortes path multiple constrained (optimal) path qos-aware multicommodity flow