zbMATH — the first resource for mathematics

Minmax regret solutions for minimax optimization problems with uncertainty. (English) Zbl 0988.90026
Summary: We propose a general approach for finding minmax regret solutions for a class of combinatorial optimization problems with an objective function of minimax type and uncertain objective function coefficients. The approach is based on reducing a problem with uncertainty to a number of problems without uncertainty. The method is illustrated on bottleneck combinatorial optimization problems, minimax multifacility location problems and maximum weighted tardiness scheduling problems with uncertainty.

90C27 Combinatorial optimization
90C31 Sensitivity, stability, parametric optimization
90C35 Programming involving graphs or networks
Full Text: DOI
[1] Averbakh, I.; Berman, O., Bottleneck Steiner subnetwork problems with k-connectivity constraints, INFORMS J. comput., 8, 4, pp 361, 366, (1996) · Zbl 0884.90142
[2] I. Averbakh, O. Berman, Minmax regret median location on a network under uncertainty, INFORMS J. Comput., to appear. · Zbl 1034.90007
[3] I. Averbakh, O. Berman, Minmax regret p-center location on a network with demand uncertainty, Working paper, University of Toronto, Faculty of Management, Toronto, 1996.
[4] Berman, O.; Handler, G.Y., Optimal minimax path of a single service unit on a network to nonservice destinations, Transp. sci., 21, 115-122, (1987) · Zbl 0631.90023
[5] Borodin, A.; El-Yaniv, R., Online computation and competitive analysis, (1998), Cambridge University Press Cambridge · Zbl 0931.68015
[6] Camerini, P.M., The minimax spanning tree problem and some extensions, Inform. process. lett., 7, 10-14, (1978) · Zbl 0373.05028
[7] Cesa-Bianchi, N.; Freund, Y.; Helmbold, D.; Haussler, D.; Schapire, R.; Warmuth, M., How to use expert advice, J. assoc. comput. Mach., 44, 3, 427-485, (1997) · Zbl 0890.68066
[8] Chang, M.S.; Tang, C.Y.; Lee, R.C.T., Solving Euclidean bottleneck biconnected edge subgraph problem by 2-relative neighborhood graphs, Discrete appl. math., 39, 1-12, (1992) · Zbl 0768.68125
[9] Chen, B.; Lin, C., Robust one-Median location problem, Networks, 31, 93-103, (1998)
[10] Chhajed, D.; Lowe, T., m-Median and m-center problems with mutual communication: solvable special cases, Oper. res., 40, S56-S66, (1992) · Zbl 0761.90064
[11] Cover, T.M., Universal portfolios, Math. finance, 1, 1, 1-29, (1991) · Zbl 0900.90052
[12] Erkut, E.; Francis, R.L.; Tamir, A., Distance constrained multifacility minimax location problems on tree networks, Networks, 22, 37-54, (1992) · Zbl 0751.90043
[13] Francis, R.L.; Lowe, T.J.; Ratliff, H.D., Distance constraints for tree network multifacility location problems, Oper. res., 26, 571-596, (1978) · Zbl 0385.90112
[14] P. Hansen, Bicriterion Path Problems, Lecture Notes in Economics and Mathematical Systems, Vol. 177, Springer, Berlin, 1980, pp. 109-127. · Zbl 0444.90098
[15] Kall, P.; Wallace, S., Stochastic programming, (1994), Wiley New York · Zbl 0812.90122
[16] A. Kolen, Tree network and planar location theory, Center for Mathematics and Computer Science, P.O.Box 4079, 1009 AB Amsterdam, The Netherlands, 1986.
[17] P. Kouvelis, G. Vairaktarakis, G. Yu, Robust 1-median location on a tree in the presence of demand and transportation cost uncertainty, Working paper 93/94-3-4, Department of Management Science and Information Systems, Graduate School of Business, The University of Texas at Austin.
[18] Kouvelis, P.; Yu, G., Robust discrete optimization and its applications, (1997), Kluwer Academic Publishers Boston · Zbl 0873.90071
[19] Labbe, M.; Thisse, J.-F.; Wendell, R.E., Sensitivity analysis in minisum facility location problems, Oper. res., 39, 6, 961-969, (1991) · Zbl 0748.90037
[20] Lawler, E.L., Combinatorial optimization: networks and matroids, (1976), Holt, Rinehart and Winston New York · Zbl 0358.68059
[21] Meggido, N., Combinatorial optimization with rational objective functions, Math. oper. res., 4, 414-424, (1979)
[22] Mirchandani, P.B.; Francis (Eds.), R.L., Discrete location theory, (1990), Wiley New York
[23] Parker, R.G.; Rardin, R.L., Guaranteed performance heuristics for bottleneck traveling salesman problem, Oper. res. lett., 2, 269-272, (1984) · Zbl 0528.90084
[24] Pinedo, M., Scheduling, (1995), Prentice-Hall New Jersey
[25] Punnen, A.P., A linear time algorithm for the maximum capacity path problem, Eur. J. oper. res., 53, 402-404, (1991) · Zbl 0732.90085
[26] Punnen, A.P.; Nair, K.P.K., A fast and simple algorithm for the bottleneck biconnected spanning subgraph problem, Inform. process. lett., 50, 283-286, (1994) · Zbl 0814.68099
[27] B. Tansel, G. Yesilkokcen, Polynomially solvable cases of multifacility distance constraints on cyclic networks, ISOLDE-6 Proceedings 1993, pp. 269-273.
[28] Vairaktarakis, G.; Kouvelis, P., Incorporation dynamic aspects and uncertainty in 1-Median location problems, Naval res. logistics, 46, 147-168, (1999) · Zbl 0918.90101
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.