Un nuevo resultado sobre la complejidad del problema delP-centro
Tóm tắt
SeaG un grafo no dirigido conn vértices ym aristas. Unp-Centro deG es un conjunto dep puntos en el que se minimiza la distancia al vértice más lejano. Esta distancia mínima es elp-Radio deG. UnCentro Local es un puntoc a la misma distancia (Ilamada rango del centro local) de un conjunto no vacío de vértices que no son todos accesibles a través de un mismo vértice adyacente ac. Todop-radio es el rango de algún centro local, por tanto, para resolver el problema delp-centro basta encontrar el menor rangor tal que existe un conjunto dep puntos que cubren a todos los vértices dentro de una distanciar. Este valorr es elp-radio y el correspondient conjunto es unp-centro. Para encontrar estos conjuntos basta considerar losr-Extremos, puntos a distanciar de algún vértice. En este trabajo se utilizan losr-extremos para construir un sencillo algoritmo de complejidadO(m
P·nP+1·logn) que es comparado experimentalmente con el procedimiento de relajación de Handler (1979).
Tài liệu tham khảo
AHO, A. V.; HOPCROFT, J. E., y ULLMAN, J. D. (1983):Data Structures and Algorithms, Addison-Wesley.
BALAS, E., y HO, A. (1980): «Set Covering Algorithms Using Cutting Planes, Heuristics and Subgradient Optimization: A Computational Study»,Math. Prog., 12, 37–60.
GONDRAN, M., y MINOUX, M. (1984):Graphs and Algorithms, John Wiley.
HAKIMI, S. L. (1965): «Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph-Theoretic Problems»,Oper. Res., 13, 462–475.
HANDLER, G. Y. (1979): «Complexity and Efficiency in Minimax Network Location»,Combinatorial Optimization (N. Christofides y Mingozzi, eds.), New York, John Wiley, 281–325.
HANDLER, G. Y., y MIRCHANDANI, P. B. (1979):Location on Networks: Theory and Algorithms, Matsachussets, M.I.T. Press.
KARIV, O., y HAKIMI, S. L. (1979): «An Algorithmic Approach to Network Location Problems. Part I: Thep-Centers»,SIAM, J. of App. Math., 37, 3, 513–538.
MINIEKA, E. (1970): «The m-Center Problem»,SIAM Review, 12, 138–139.
MORENO, J. (1985): «A Correction to the Definition of Local Center»,Eur. J. of Oper. Res., 20, 382–386.
MORENO, J. (1986):Localización Minimax en Grafos Mixtos, Tesis Doctoral, Universidad Complutense de Madrid.
SYSLO, M. M.; DEO, N., y KOWALIK, J. S. (1983):Discrete Optimization Algorithms with Pascal Programs, New Jersey, Prenticel-Hall.
TAMIR, A. (1987): «Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures», Presentado a ISOLDE IV, Namur, Bélgica.
TARJAN, R. E. (1983):Data Structures and Network Algorithms, New Jersey, Society for Industrial and Applied Mathematics.
VASKO, F. J., y WILSON, G. R. (1984): «An Efficient Heuristic for Large Set Covering Problems»,Naval Research Logistic Quarterly, 31, 163–171.