Computing Min-Max Regret Solutions in Possibilistic Combinatorial Optimization Problems

1. Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs (1993)

   Google Scholar 

2. Aissi, H., Bazgan, C., Vanderpooten, D.: Min-max and min-max regret versions of combinatorial optimization problems: A survey. European Journal of Operational Research (2008) doi:10.1016/j.ejor.2008.09.012

   Google Scholar 

3. Aissi, H., Bazgan, C., Vanderpooten, D.: Complexity of the min-max and min-max regret assignment problems. Operations Research Letters 33(6), 634–640 (2005)

   Article  MATH  MathSciNet  Google Scholar 

4. Aissi, H., Bazgan, C., Vanderpooten, D.: Complexity of the min-max (regret) versions of cut problems. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol. 3827, pp. 789–798. Springer, Heidelberg (2005)

   Chapter  Google Scholar 

5. Aron, I.D., Hentenryck, P.V.: A constraint satisfaction approach to the robust spanning tree problem with interval data. In: Darwiche, A., Friedman, N. (eds.) UAI 2002, Proceedings of the 18th Conference in Uncertainty in Artificial Intelligence, University of Alberta, Edmonton, Alberta, Canada, August 1-4, pp. 18–25. Morgan Kaufmann, San Francisco (2002)

   Google Scholar 

6. Aron, I.D., Hentenryck, P.V.: On the complexity of the robust spanning tree problem with interval data. Operations Research Letters 32(1), 36–40 (2004)

   Article  MATH  MathSciNet  Google Scholar 

7. Averbakh, I.: Minmax regret solutions for minimax optimization problems with uncertainty. Operations Research Letters 27(2), 57–65 (2000)

   Article  MATH  MathSciNet  Google Scholar 

8. Averbakh, I.: On the complexity of a class of combinatorial optimization problems with uncertainty. Mathematical Programming 90, 263–272 (2001)

   Article  MATH  MathSciNet  Google Scholar 

9. Averbakh, I., Lebedev, V.: On the complexity of minmax regret linear programming. European Journal of Operational Research 160(1), 227–231 (2005)

   Article  MATH  MathSciNet  Google Scholar 

10. Camerini, P.M.: The minimax spanning tree problem and some extensions. Information Processing Letters 7, 10–14 (1978)

    Article  MATH  MathSciNet  Google Scholar 

11. Chan, T.: Finding the shortest bottleneck edge in a parametric minimum spanning tree. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 232–240 (2005)

    Google Scholar 

12. Conde, E.: An improved algorithm for selecting p items with uncertain returns according to the minmax-regret criterion. Mathematical Programming 100(2), 345–353 (2004)

    Article  MATH  MathSciNet  Google Scholar 

13. Dubois, D., Fargier, H., Galvagnon, V.: On latest starting times and floats in activity networks with ill-known durations. European Journal of Operational Research 147, 266–280 (2003)

    Article  MATH  MathSciNet  Google Scholar 

14. Dubois, D., Prade, H.: Possibility Theory: An Approach to Computerized Processing of Uncertainty. Plenum Press (1988)

    Google Scholar 

15. Fernandez-Baca, D., Slutzki, G.: Solving parametric problems on trees. Journal of Algorithms 10 (1989)

    Google Scholar 

16. Fortin, J., Zieliński, P., Dubois, D., Fargier, H.: Interval analysis in scheduling. In: van Beek, P. (ed.) CP 2005. LNCS, vol. 3709, pp. 226–240. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

17. Gabow, H.N., Tarjan, R.E.: Algorithms for two bottleneck optimization problems. Journal of Algorithms 9, 411–417 (1988)

    Article  MATH  MathSciNet  Google Scholar 

18. Garfinkel, R.S., Nemhauser, G.L.: Integer Programming. John Wiley & Sons, Chichester (1972)

    MATH  Google Scholar 

19. Inuiguchi, M.: On possibilistic/fuzzy optimization. In: Melin, P., Castillo, O., Aguilar, L.T., Kacprzyk, J., Pedrycz, W. (eds.) IFSA 2007. LNCS (LNAI), vol. 4529, pp. 351–360. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

20. Inuiguchi, M., Sakawa, M.: Robust optimization under softness in a fuzzy linear programming problem. International Journal of Approximate Reasonning 18(1-2), 21–34 (1998)

    Article  MATH  MathSciNet  Google Scholar 

21. Kall, P., Wallace, S.W.: Stochastic Programming. Wiley, Chichester etc. (1994)

    MATH  Google Scholar 

22. Kasperski, A.: Discrete Optimization with Interval Data. Minmax Regret and Fuzzy Approach. Studies in Fuzziness and Soft Computing, vol. 228. Springer, Heidelberg (2008)

    MATH  Google Scholar 

23. Kasperski, A., Zieliński, P.: An approximation algorithm for interval data minmax regret combinatorial optimization problems. Information Processing Letters 97(5), 177–180 (2006)

    Article  MATH  MathSciNet  Google Scholar 

24. Kasperski, A., Zieliński, P.: The robust shortest path problem in series-parallel multidigraphs with interval data. Operations Research Letters 34(1), 69–76 (2006)

    Article  MATH  MathSciNet  Google Scholar 

25. Kasperski, A., Zieliński, P.: On combinatorial optimization problems on matroids with uncertain weights. European Journal of Operational Research 177(2), 851–864 (2007)

    Article  MATH  MathSciNet  Google Scholar 

26. Kasperski, A., Zieliński, P.: On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data. Operations Research Letters 35(4), 525–532 (2007)

    Article  MATH  MathSciNet  Google Scholar 

27. Kasperski, A., Zieliński, P.: Using gradual numbers for solving fuzzy-valued combinatorial optimization problems. In: Melin, P., Castillo, O., Aguilar, L.T., Kacprzyk, J., Pedrycz, W. (eds.) IFSA 2007. LNCS (LNAI), vol. 4529, pp. 656–665. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

28. Kasperski, A., Zieliński, P.: Minmax regret approach and optimality evaluation in combinatorial optimization problems with interval and fuzzy weights. European Journal of Operational Research (2009) (to appear)

    Google Scholar 

29. Kouvelis, P., Yu, G.: Robust Discrete Optimization and Its Applications. Kluwer Academic Publishers, Boston (1997)

    MATH  Google Scholar 

30. Lawler, E.: Combinatorial Optimization: Networks and Matroids. Saunders College Publishing, Fort Worth (1976)

    MATH  Google Scholar 

31. Luce, R.D., Raiffa, H.: Games and Decisions. Introduction and Critical Survey. Dover Publications, Inc., New York (1957)

    MATH  Google Scholar 

32. Montemanni, R.: A benders decomposition approach for the robust spanning tree problem with interval data. European Journal of Operational Research 174(3), 1479–1490 (2006)

    Article  MATH  MathSciNet  Google Scholar 

33. Montemanni, R., Gambardella, L.M.: A branch and bound algorithm for the robust spanning tree problem with interval data. European Journal of Operational Research 161(3), 771–779 (2005)

    Article  MATH  MathSciNet  Google Scholar 

34. Montemanni, R., Gambardella, L.M., Donati, A.V.: A branch and bound algorithm for the robust shortest path problem with interval data. Operations Research Letters 32(3), 225–232 (2004)

    Article  MATH  MathSciNet  Google Scholar 

35. Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Dover Pub. (1998)

    Google Scholar 

36. Punnen, A.P.: A linear time algorithm for the maximum capacity path problem. European Journal of Operational Research 53, 402–404 (1991)

    Article  MATH  Google Scholar 

37. Punnen, A.P.: A fast algorithm for a class of bottleneck problems. Computing 56, 397–401 (1996)

    Article  MATH  MathSciNet  Google Scholar 

38. Raghavan, S., Ball, M.O., Trichur, V.S.: Bicriteria product design optimization: An efficient solution procedure using and/or trees. Naval Research Logistics 49, 574–592 (2002)

    Article  MATH  MathSciNet  Google Scholar 

39. Savage, L.J.: The Foundations of Statistics. John Wiley and Sons, New York (1951)

    Google Scholar 

40. Yaman, H., Karasan, O.E., Pinar, M.Ç.: The robust spanning tree problem with interval data. Operations Research Letters 29(1), 31–40 (2001)

    Article  MATH  MathSciNet  Google Scholar 

41. Young, N., Tarjan, R., Orlin, J.: Faster parametric shortest path minimum-balance algorithms. Networks 21, 205–221 (1991)

    Article  MATH  MathSciNet  Google Scholar 

42. Zieliński, P.: The computational complexity of the relative robust shortest path problem with interval data. European Journal of Operational Research 158(3), 570–576 (2004)

    Article  MATH  MathSciNet  Google Scholar 

Download references