A model for the inverse 1-median problem on trees under uncertain costs

• Autorzy: Nguyen K. T. , Chi N. T. L.

Identyfikatory

DOI

10.7494/OpMath.2016.36.4.513

• Języki publikacji: EN

Abstrakty

EN

We consider the problem of justifying vertex weights of a tree under uncertain costs so that a prespecified vertex become optimal and the total cost should be optimal in the uncertainty scenario. We propose a model which delivers the information about the optimal cost which respect to each confidence level α ∈ [0,1]. To obtain this goal, we first define an uncertain variable with respect to the minimum cost in each confidence level. If all costs are independently linear distributed, we present the inverse distribution function of this uncertain variable in [formula]time, where n is the number of vertices in the tree.

Słowa kluczowe

EN

location problem; uncertain variable; inverse optimization problem; tree

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2016
• Tom: Vol. 36, no. 4
• Strony: 513--523
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Nguyen K. T.

• Cantho University Mathematics Department Teacher College Cantho, Vietnam

autor

Chi N. T. L.

• Cantho University Mathematics Department Science College Cantho, Vietnam

Bibliografia

• [1] B. Alizadeh, R.E. Burkard, Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees, Networks 58 (2011), 190-200.
• [2] B. Alizadeh, R.E. Burkard, Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees, Discrete Appl. Math. 159 (2011), 706-716.
• [3] B. Alizadeh, R.E. Burkard, U. Pferschy, Inverse 1-center location problems with edge length augmentation on trees, Computing 86 (2009), 331-343.
• [4] E. Balas, E. Zemel, An algorithm, for large zero-one knapsack problems, Operations Research 28 (1980), 1130-1154.
• [5] F.B. Bonab, R.E. Burkard, E. Gassner, Inverse p-median problems with variable edge lengths, Math. Meth. Oper. Res. 73 (2011), 263-280.
• [6] R.E. Burkard, C. Pleschiutschnig, J.Z. Zhang, Inverse median problems, Discrete Optimization 1 (2004), 23-39.
• [7] R.E. Burkard, C. Pleschiutschnig, J.Z. Zhang, The inverse 1-median problem on a cycle, Discrete Optimization 5 (2008), 242-253.
• [8] M.C. Cai, X.G. Yang, J.Z. Zhang, The complexity analysis of the inverse center location problem, J. Global Optimization 15 (1999), 213-218.
• [9] M. Galavii, The inverse 1-median problem on a tree and on a path, Electronic Notes in Disrete Mathematics 36 (2010), 1241-1248.
• [10] Y. Gao, Shortest path problem with uncertain arc lengths, Computers and Mathematics with Applications 62 (2011), 2591-2600.
• [11] A.J. Goldman, Optimal center location in simple networks, Transportation Science 5 (1971), 539-560.
• [12] L.K. Hua, Application of mathematical models to wheat harvesting, Chinese Mathematics 2 (1962), 539-560.
• [13] B. Liu, Uncertainty Theory, 2nd ed., Springer-Verlag, Berlin, 2007.
• [14] B. Liu, Some research problems in uncertainty theory, Journal of Uncertain Systems 3 (2009), 3-10.
• [15] K.T. Nguyen, A. Chassein, Inverse eccentric vertex problem, on networks, Cent. Eur. Jour. Oper. Res. 23 (2015), 687-698.
• [16] K.T. Nguyen, L.Q. Anh, Inverse k-centrum problem on trees with variable vertex weights, Math. Meth. Oper. Res. 82 (2015), 19-30.
• [17] K.T. Nguyen, A.R. Sepasian, The inverse 1-center problem on trees under Ghebyshev norm, and Hamming distance, Journal of Combinatorial Optimization (2015), DOI: 10.1007/sl0878-015-9907-5.
• [18] K.T. Nguyen, Reverse 1-center problem on weighted trees, Optimization 65 (2016), 253-264.
• [19] J. Zhou, F. Yang, K. Wang, An inverse shortest path problem on an uncertain graph, Journal of Networks 9 (2014), 2353-2359.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.