Advertisement

Recent Advances in Multiobjective Optimization

  • Christos Zaroliagis
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3777)

Abstract

Multiobjective (or multicriteria) optimization is a research area with rich history and under heavy investigation within Operations Research and Economics in the last 60 years [1,2]. Its object of study is to investigate solutions to combinatorial optimization problems that are evaluated under several objective functions – typically defined on multidimensional attribute (cost) vectors. In multiobjective optimization, we are interested not in finding a single optimal solution, but in computing the trade-off among the different objective functions, called the Pareto set (or curve) \({\mathcal P}\), which is the set of all feasible solutions whose vector of the various objectives is not dominated by any other solution.

Keywords

Multiobjective Optimization Short Path Problem Multiobjective Optimization Problem Span Tree Problem Pareto Curve 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Ehrgott, M.: Multicriteria Optimization. Springer, Heidelberg (2000)zbMATHGoogle Scholar
  2. 2.
    Ehrgott, M., Gandibleux, X. (eds.): Multiple Criteria Optimization – state of the art annotated bibliographic surveys. Kluwer Academic Publishers, Boston (2002)zbMATHGoogle Scholar
  3. 3.
    Etzioni, O., Hanks, S., Jiang, T., Karp, R., Madari, O., Waarts, O.: Efficient Information Gathering on the Internet. In: Proc. 37th IEEE Symp. on Foundations of Computer Science – FOCS 1996, pp. 234–243 (1996)Google Scholar
  4. 4.
    Handler, G., Zang, I.: A Dual Algorithm for the Constrained Shortest Path Problem. Networks 10, 293–310 (1980)CrossRefMathSciNetGoogle Scholar
  5. 5.
    Hansen, P.: Bicriterion Path Problems. In: Proc. 3rd Conf. Multiple Criteria Decision Making – Theory and Applications. LNEMS, vol. 117, pp. 109–127. Springer, Heidelberg (1979)Google Scholar
  6. 6.
    Marathe, M., Ravi, R., Sundaram, R., Ravi, S.S., Rosenkrantz, D., Hunt, H.B.: Bicriteria Network Design Problems. Journal of Algorithms 28, 142–171 (1998)zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    Papadimitriou, C., Yannakakis, M.: On the Approximability of Trade-offs and Optimal Access of Web Sources. In: Proc. 41st IEEE Symp. on Foundations of Computer Science – FOCS 2000, pp. 86–92 (2000)Google Scholar
  8. 8.
    Ravi, R., Marathe, M., Ravi, S.S., Rosenkrantz, D., Hunt, H.B.: Many Birds with One Stone: Multi-objective Approximation Algorithms. In: Proc. 25th ACM Symp. on Theory of Computing – STOC 1993, pp. 438–447 (1993)Google Scholar
  9. 9.
    Tsaggouris, G., Zaroliagis, C.: Non-Additive Shortest Paths. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 822–834. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  10. 10.
    Tsaggouris, G., Zaroliagis, C.: Improved FPTAS for Multiobjective Shortest Paths with Applications. CTI Technical Report TR 2005/07/03 (July 2005)Google Scholar
  11. 11.
    Vassilvitskii, S., Yannakakis, M.: Efficiently Computing Succinct Trade-off Curves. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 1201–1213. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  12. 12.
    Warburton, A.: Approximation of Pareto Optima in Multiple-Objective Shortest Path Problems. Operations Research 35, 70–79 (1987)zbMATHCrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Christos Zaroliagis
    • 1
    • 2
  1. 1.Computer Technology InstitutePatrasGreece
  2. 2.Department of Computer Engineering and InformaticsUniversity of PatrasPatrasGreece

Personalised recommendations