Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-Linear Objectives with Applications

1. Ackermann, H., Newman, A., Röglin, H., Vöcking, B.: Decision making based on approximate and smoothed Pareto curves. In: Algorithms and Computation, ISAAC 2005. Lecture Notes in Computer Science, vol. 3827, pp. 675–684. Springer, Berlin (2006). Full version as Tech. Report AIB-2005-23, RWTH Aachen, December (2005)

   Chapter  Google Scholar 

2. Beckmann, M., McGuire, G., Winsten, C.: Studies in the Economics of Transportation. Yale University Press, New Haven (1956)

   Google Scholar 

3. Chaudhuri, K., Papadimitriou, C., Rao, S.: Optimum routing with quality of service constraints. Manuscript (2004)

4. Corley, H., Moon, I.: Shortest paths in networks with vector weights. J. Optim. Theory Appl. 46(1), 79–86 (1985)

   Article  MATH  MathSciNet  Google Scholar 

5. Dafermos, S.: The general multimodal network equilibrium problem with elastic demands. Networks 12, 57–72 (1982)

   Article  MATH  MathSciNet  Google Scholar 

6. Datta, A., Vandermeer, D., Celik, A., Kumar, V.: Broadcast protocols to support efficient retrieval from databases by mobile users. ACM Trans. Database Syst. 24(1), 1–79 (1999)

   Article  Google Scholar 

7. Ehrgott, M.: Multicriteria Optimization. Springer, Berlin (2000)

   MATH  Google Scholar 

8. Ehrgott, M., Gandibleux, X. (eds.): Multiple Criteria Optimization—State of the Art Annotated Bibliographic Surveys. Kluwer Academic, Boston (2002)

   MATH  Google Scholar 

9. Ergun, F., Sinha, R., Zhang, L.: An improved FPTAS for restricted shortest path. Inf. Process. Lett. 83, 287–291 (2002)

   Article  MATH  MathSciNet  Google Scholar 

10. Figueira, J., Greco, S., Ehrgott, M. (eds.): Multiple Criteria Decision Analysis—State of the Art Surveys. Springer, Boston (2005)

    MATH  Google Scholar 

11. Fleischer, L.K.: Approximating fractional multicommodity flows independent of the number of commodities. SIAM J. Discrete Math. 13(4), 505–520 (2000)

    Article  MATH  MathSciNet  Google Scholar 

12. Florian, M., Nguyen, S.: A method for computing network equilibrium with elastic demands. Transp. Sci. 8, 321–332 (1974)

    Article  MathSciNet  Google Scholar 

13. Gabriel, S., Bernstein, D.: The traffic equilibrium problem with nonadditive path costs. Transp. Sci. 31(4), 337–348 (1997)

    Article  MATH  Google Scholar 

14. Gabriel, S., Bernstein, D.: Nonadditive shortest paths: subproblems in multi-agent competitive network models. Comput. Math. Organ. Theory 6, 29–45 (2000)

    Article  Google Scholar 

15. Garg, N., Könemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In: Proc. 39th IEEE Symposium on Foundations of Computer Science, FOCS’98, pp. 300–309. IEEE CS Press (1998)

16. Garg, N., Könemann, J.: Personal communication (2005)

17. Goel, A., Ramakrishnan, K.G., Kataria, D., Logothetis, D.: Efficient computation of delay-sensitive routes from one source to all destinations. In: Proc. IEEE Conf. Comput. Commun. INFOCOM (2001)

18. Hansen, P.: Bicriterion Path Problems. In: Theory and Applications. Proc. 3rd Conf. Multiple Criteria Decision Making. Lecture Notes in Economics and Mathematical Systems, vol. 117, pp. 109–127. Springer, Berlin (1979)

    Google Scholar 

19. Hassin, R.: Approximation schemes for the restricted shortest path problem. Math. Oper. Res. 17, 36–42 (1992)

    Article  MATH  MathSciNet  Google Scholar 

20. Hensen, D., Truong, T.: Valuation of travel times savings. J. Transp. Econ. Policy 237–260 (1985)

21. Korkmaz, T., Kruz, M.: Multiconstrained optimal path selection. In: Proc. IEEE Conf. Comput. Commun. INFOCOM, pp. 834–843 (2001)

22. Lorenz, D.H., Raz, D.: A simple efficient approximation scheme for the restricted shortest path problem. Oper. Res. Lett. 28, 213–219 (2001)

    Article  MATH  MathSciNet  Google Scholar 

23. Van Mieghem, P., Kuipers, F.A., Korkmaz, T., Krunz, M., Curado, M., Monteiro, E., Masip-Bruin, X., Sole-Pareta, J., Sanchez-Lopez, S.: Quality of service routing. In: Quality of Future Internet Services. Lecture Notes in Computer Science, vol. 2856, pp. 80–117. Springer, Berlin (2003)

    Google Scholar 

24. Papadimitriou, C., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. In: Proc. 41st Symp. on Foundations of Computer Science, FOCS, pp. 86–92 (2000)

25. PIN project (Projekt Integrierte Netzoptimierung): Deutsche Bahn AG (2000)

26. Scott, K., Bernstein, D.: Solving a best path problem when the value of time function is nonlinear. Preprint 980976 of the Annual Meeting of the Transportation Research Board (1997)

27. Tsaggouris, G., Zaroliagis, C.: Improved FPTAS for multiobjective shortest paths with applications. CTI Techn. Report TR-2005/07/03, July (2005)

28. Tsaggouris, G., Zaroliagis, C.: QoS-aware multicommodity flows and transportation planning. In: Proc. 6th Workshop on Algorithmic Methods and Models for Optimization of Railways, ATMOS (2006)

29. Tsaggouris, G., Zaroliagis, C.: Multiobjective optimization: Improved FPTAS for shortest paths and non-linear objectives with applications. In: Algorithms and Computation, ISAAC 2006. Lecture Notes in Computer Science, vol. 4288, pp. 389–398. Springer, Berlin (2006)

    Chapter  Google Scholar 

30. Vassilvitskii, S., Yannakakis, M.: Efficiently computing succinct trade-off curves. In: Automata, Languages, and Programming, ICALP 2004. Lecture Notes in Computer Science, vol. 3142, pp. 1201–1213. Springer, Berlin (2004)

    Google Scholar 

31. Wagner, F.: Challenging optimization problems at deutsche bahn. AMORE Workshop (invited talk) (1999)

32. Warburton, A.: Approximation of Pareto optima in multiple-objective shortest path problems. Oper. Res. 35, 70–79 (1987)

    Article  MATH  MathSciNet  Google Scholar 

33. Young, N.: Sequential and parallel algorithms for mixed packing and covering. In: Proc. 42nd IEEE Symp. on Foundations of Computer Science, FOCS, pp. 538–546 (2001)

Download references