The inverse 1-center problem on cycles with variable edge lengths. (English) Zbl 1464.90084
Summary: We consider the problem of modifying edge lengths of a cycle at minimum total costs so as to make a prespecified vertex an (absolute) 1-center of the cycle with respect to the new edge legths. We call this problem the inverse 1-center problem on a cycle. To solve this problem, we first construct the so-called optimality criterion for a vertex to be a 1-center. Based on the optimality criterion, it is shown that the problem can be separated into linearly many subproblems. For a predetermined subproblem, we apply a parameterization approach to formulate it as a minimization problem of a piecewise linear convex function with a connected feasible region. Hence, it is shown that the problem can be solved in \(O(n^2 \log n)\) time, where \(n\) is the number of vertices in the cycle.
MSC:
| 90C27 | Combinatorial optimization |
| 90B10 | Deterministic network models in operations research |
| 90B80 | Discrete location and assignment |
References:
| [1] | Alizadeh B, Bakhteh S (2016) A modified firefly algorithm for general inverse \[p\] p-median location problems under different distance norms. OPSEARCH. https://doi.org/10.1007/s12597-016-0296-z · Zbl 1397.90406 · doi:10.1007/s12597-016-0296-z |
| [2] | Alizadeh B, Burkard RE (2011a) Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees. Networks 58(3):190-200. https://doi.org/10.1002/net.20427 · Zbl 1236.90094 · doi:10.1002/net.20427 |
| [3] | Alizadeh B, Burkard RE (2011b) Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees. Discrete Appl. Math. 159:706-716. https://doi.org/10.1016/j.dam.2011.01.009 · Zbl 1220.90104 |
| [4] | Alizadeh B, Burkard RE (2012) A linear time algorithm for inverse obnoxious center location problems on networks. Cent. Eur. J. Oper. Res. 2013:585-594. https://doi.org/10.1007/s10100-012-0248-5 · Zbl 1339.90188 · doi:10.1007/s10100-012-0248-5 |
| [5] | Alizadeh B, Burkard RE, Pferschy U (2009) Inverse 1-center location problems with edge length augmentation on trees. Computing 86:331-343. https://doi.org/10.1007/s00607-009-0070-7 · Zbl 1180.90163 · doi:10.1007/s00607-009-0070-7 |
| [6] | Bonab FB, Burkard RE, Gassner E (2011) Inverse \[p\] p-median problems with variable edge lengths. Math. Methods Oper. Res. 73:263-280. https://doi.org/10.1007/s00186-011-0346-5 · Zbl 1216.49032 · doi:10.1007/s00186-011-0346-5 |
| [7] | Burkard RE, Pleschiutschnig C, Zhang JZ (2008) The inverse 1-median problem on a cycle. Discrete Opt. 5:242-253. https://doi.org/10.1016/j.disopt.2006.11.008 · Zbl 1177.90245 · doi:10.1016/j.disopt.2006.11.008 |
| [8] | Burkard RE, Pleschiutschnig C, Zhang JZ (2014) Inverse median problems. Discrete Opt. 1:23-39. https://doi.org/10.1016/j.disopt.2004.03.003 · Zbl 1087.90038 · doi:10.1016/j.disopt.2004.03.003 |
| [9] | Galavii M (2010) The inverse 1-median problem on a tree and on a path. Electron. Notes Disrete Math. 36:1241-1248. https://doi.org/10.1016/j.endm.2010.05.157 · Zbl 1274.90305 · doi:10.1016/j.endm.2010.05.157 |
| [10] | Gassner E (2012) An inverse approach to convex ordered median problems in trees. J. Comb. Opt. 23(2):261-273. https://doi.org/10.1007/s10878-010-9353-3 · Zbl 1243.90223 · doi:10.1007/s10878-010-9353-3 |
| [11] | Guan X, Zhang B (2011) Inverse 1-median problem on trees under weighted Hamming distance. J. Glob. Opt. 54:75-82. https://doi.org/10.1007/s10898-011-9742-x · Zbl 1273.90237 · doi:10.1007/s10898-011-9742-x |
| [12] | Kariv O, Hakimi SL (1979a) An algoithmic approach to network location problems, I. The p-centers. SIAM J. Appl. Math. 37:513-538. https://doi.org/10.1137/0137040 · Zbl 0432.90074 · doi:10.1137/0137040 |
| [13] | Kariv O, Hakimi SL (1979b) An algoithmic approach to network location problems, II. The p-medians. SIAM J. Appl. Math. 37:536-560. https://doi.org/10.1137/0137041 · Zbl 0432.90075 · doi:10.1137/0137041 |
| [14] | Nguyen KT (2016) Inverse 1-median problem on block graphs with variable vertex weights. J. Optim. Theory Appl. 168:944-957. https://doi.org/10.1007/s10957-015-0829-2 · Zbl 1338.90085 · doi:10.1007/s10957-015-0829-2 |
| [15] | Nguyen KT, Anh LQ (2015) Inverse \[k\] k-centrum problem on trees with variable vertex weights. Math. Meth. Oper. Res. 82:19-30. https://doi.org/10.1007/s00186-015-0502-4 · Zbl 1330.90120 |
| [16] | Nguyen KT, Chassein A (2015a) Inverse eccentric vertex problem on networks. Cent. Eur. J. Oper. Res. 23:687-698. https://doi.org/10.1007/s10100-014-0367-2 · Zbl 1339.90286 · doi:10.1007/s10100-014-0367-2 |
| [17] | Nguyen KT, Chassein A (2015b) The inverse convex ordered 1-median problem on trees under Chebyshev norm and Hamming distance. Eur. J. Oper. Res. 247:774-781. https://doi.org/10.1016/j.ejor.2015.06.064 · Zbl 1346.90712 |
| [18] | Nguyen KT, Chi NTL (2016) A model for the inverse 1-median problem on trees under uncertain costs. Opuscula Math. 36:513-523. https://doi.org/10.7494/OpMath.2016.36.4.513 · Zbl 1338.90086 · doi:10.7494/OpMath.2016.36.4.513 |
| [19] | Nguyen KT, Sepasian AR (2015) The inverse 1-center problem on trees under Chebyshev norm and Hamming distance. J. Comb. Opt. 32:872-884. https://doi.org/10.1007/s10878-015-9907-5 · Zbl 1354.90113 |
| [20] | Sepasian AR, Rahbarnia F (2015) An \[O(n\log n)O\](nlogn) algorithm for the inverse 1-median problem on trees with variable vertex weights and edge reductions. Optimization 64:595-602. https://doi.org/10.1080/02331934.2013.783033 · Zbl 1308.90028 · doi:10.1080/02331934.2013.783033 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
