 |
S.I. Fainshtein, A.S. Fainshtein, V.E. Torchinsky "Weighted Admissible Absolute 1-Center Problem" |
 |
|
Abstract. This paper presents a polynomial algorithm for new generalization of the absolute 1-center problem (A1CP) in general undirected graph with each edge having a positive weight vector (length for the first coordinate and costs for all the other coordinates) and with each vertex having non-negative weight vector. We assume that the cost is a linear function of the length on edge. Non-negative cost boundaries are also given. AA1CP (admissible absolute 1-center problem) minimizes the weighted length of path between a point on edge and the farthest vertex provided that any weighted cost of path from the point to any vertex does not exceed the corresponding cost boundary.
Keywords: vertex-weighted absolute 1-center problem, admissible absolute 1-center problem. PP. 3-9.
DOI 10.14357/20718632200201 References
1. Hakimi, S.L. 1964. Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph. Operations Research 12:450–459. doi:10.1287/opre.12.3.450. 2. Kariv, O. & Hakimi, S.L. 1979. Algorithmic approach to network location problems, I: The p-Centers, SIAM J. Appl. Math. 37(3):513–537. doi:10.1137/0137040. 3. Goldman, A.J. Minimax location of a facility in a network. Transp. Sci. 6(4):407–418. doi:10.1287/trsc.6.4.407. 4. Megiddo, N. 1983. Linear-time algorithms for linear programming in R3 and related problems. SIAMJ. Comput. 12(4): 759–776. doi:10.1137/0212052. 5. Ding, W. & Qiu., K. 2017. FPTAS for generalized absolute 1-center problem in vertex-weighted graphs. Journal of Combinatorial Optimization. 34(4):1084–1095. doi: 10.1007/s10878-017-0130-4. 6. Ramos, R.M., Sicilia, J. & Ramos, M.T. 1997. The biobjective absolute center problem. TOP, 5(2): 187-199. doi: 10.1007/BF02568548. 7. Ding, W. & Qiu., K. 2015. Approximating the Restricted 1-Center in Graphs. In: Lu Z., Kim D., Wu W., Li W., Du DZ. (eds) Combinatorial Optimization and Applications. Lecture Notes in Computer Science, vol 9486: 647-659. doi: 10.1007/978-3-319-26626-8_47. 8. Minieka, E. 1981. Polynomial Time Algorithm for Finding the Absolute Center of a Network. Networks, 11: 351-355. doi:10.1002/net.3230110404 9. Minieka, E. 1978. Optimization Algorithms for Networks and Graphs. New York: Marcel Dekker. 356 p. 10. Christofides, N. 1975. Graph Theory: Algorithmic Approach. New York: Academic. 400 p. 11. Torchinsky, V.E. & Fainshtein, S.I. 2007. Struktury i algoritmy obrabotki dannykh na EVM [Structures and algorithms of computer data processing]. Magnitogorsk: Magnitogorsk State Univ. 139 p.
|
