МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
S.I. Fainshtein, A.S. Fainshtein, V.E. Torchinsky Weighted admissible absolute 1-center problem
МЕТОДЫ ОБРАБОТКИ ИЗОБРАЖЕНИЙ
СИСТЕМЫ УПРАВЛЕНИЯ
ПРИКЛАДНЫЕ АСПЕКТЫ ИНФОРМАТИКИ
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 
 
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.
 
2020 / 02
2020 / 01
2019 / 04
2019 / 03

© ФИЦ ИУ РАН 2008-2018. Создание сайта "РосИнтернет технологии".