×

zbMATH — the first resource for mathematics

Algorithms for the robust 1-center problem on a tree. (English) Zbl 0967.90065
Summary: We consider the weighted 1-center problem on a network with uncertainty in node weights and edge lengths. Uncertainty is modelled by means of interval estimates for parameters. Specifically, each uncertain parameter is assumed to be random with unknown distribution and can take on any value within a corresponding prespecified interval. It is required to find a robust (minmax regret) solution, that is, a location which is \(\varepsilon\)-optimal for any possible realization of parameters, with \(\varepsilon\) as small as possible. The problem on a general network is known to be NP-hard; for the problem on a tree, we present a polynomial algorithm.

MSC:
90B80 Discrete location and assignment
90B10 Deterministic network models in operations research
PDF BibTeX Cite
Full Text: DOI
References:
[1] I. Averbakh, On the complexity of a class of robust location problems, Working Paper, Western Washington University, Bellingham, WA, 1997
[2] I. Averbakh, O. Berman, Minimax regret p-center location on a network with demand uncertainty, Location Science, to appear · Zbl 0928.90042
[3] I. Averbakh, O. Berman, Minmax regret robust median location on a network under uncertainty, Presented at INFORMS Meeting in Atlanta, 3-6 November, 1996
[4] B. Chen, C. Lin, Robust one-median location problem, Networks 31 (1998) 93-103 · Zbl 0930.90050
[5] P.B. Mirchandani, R.L. Francis (Eds.), Discrete Location Theory, Wiley, New York, 1990 · Zbl 0718.00021
[6] Drezner, Z., Sensitivity analysis of the optimal location of a facility, Naval research logistics quarterly, 33, 209-224, (1985) · Zbl 0578.90022
[7] Dyer, M.E., Linear time algorithms for two- and three-variable linear programs, SIAM J. computing, 13, 31-45, (1984) · Zbl 0532.90063
[8] Frank, H., Optimum locations on a graph with probabilistic demands, Operations research, 14, 409-421, (1966) · Zbl 0142.17704
[9] Frank, H., Optimum locations on a graph with correlated normal demands, Operations research, 14, 552-557, (1967) · Zbl 0152.38204
[10] Goldman, A.J., Optimal center locations in simple networks, Transportation science, 5, 212-221, (1971)
[11] Handler, G.Y.; Mirchandani, P.B., Location on networks: theory and algorithms, (1979), MIT Press Cambridge, MA · Zbl 0533.90026
[12] O. Kariv, S.L. Hakimi, An algorithmic approach to network location problems, part 1. The p-centers, SIAM Journal on Applied Mathematics 37 (1979) 513-538 · Zbl 0432.90074
[13] 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
[14] Kouvelis, P.; Yu, G., Robust discrete optimization and its applications, (1997), Kluwer Academic Publishers Dordrecht · Zbl 0873.90071
[15] Labbe, M.; Thisse, J.-F.; Wendell, R., Sensitivity analysis in minisum facility location problems, Operations research, 39, 961-969, (1991) · Zbl 0748.90037
[16] M. Labbe, D. Peeters, J.-F. Thisse, Location on networks, in: Handbooks in Operations Research and Management Science, vol. 8, Elsevier, Amsterdam, 1995, 551-624 · Zbl 0862.90088
[17] Megiddo, N., Linear time algorithms for linear programming in R^{3} and related problems, SIAM journal of computing, 12, 759-776, (1983) · Zbl 0521.68034
[18] Mirchandani, P.B.; Odoni, A.R., Location of medians on stochastic networks, Transportation science, 13, 85-97, (1979)
[19] J.M. Mulvey, R.J. Vanderbei, S.A. Zenios, Robust optimization of large scale systems, Operations Research 43 (1995) 264-281 · Zbl 0832.90084
[20] B. Tansel, G. Scheuenstuhl, Facility location on tree networks with imprecise data. Research Report IEOR-8819, Bilkent University, Ankara, 1988
[21] Wesolowsky, G.O., Probabilistic weights in the one-dimensional facility location problem, Management science, 24, 224-229, (1977) · Zbl 0372.90068
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.