El problema del K-centro en RN con normas LPB estrictas

Resumen

SE PLANTEA EL PROBLEMA DE ENCONTRAR UN CONJUNTO C DE K PUNTOS EN IRN, TAL QUE LA DISTANCIA MAXIMA ENTRE C Y CADA ELEMENTO DE UN CONJUNTO FINITO DADO A SEA MINIMA, APLICACIONES PUEDEN ENCONTRARSE EN LOCALIZACION DE SERVICIOS DE EMERGENCIA, CENTROS DE TRANSMISION MULTIONDA Y CLASIFICACION DE DATOS. SE ESTUDIA EL PROBLEMA CUANDO LA DISTANCIA VIENE MEDIDA POR UNA NORMA LPB CON 1<P<INFINITO, B=(B1,..., BN), BJ 0, J=L,...,N. PARA K=1, SE OBTIENEN ALGORITMOS PRIMALES Y DUALES BASADOS RESPECTIVAMENTE EN EL METODO DE DIRECCIONES FACTIBLES Y EN LA DETERMINACION DE UNA SOLUCION OPTIMA MEDIANTE N+1 PUNTOS DEL CONJUNTO A. PARA K L, SE DEMUESTRA QUE EL PROBLEMA ES EQUIVALENTE A UN PROBLEMA DE OPTIMIZACION DISCRETA, Y SE PRESENTA UN ALGORITMO EXACTO PARA SU RESOLUCION, QUE SOLO ES VIABLE PARA A<IR2 Y M<100, DEBIDO A LA NP-DUREZA DEL PROBLEMA. PARA LA OBTENCION DE SOLUCIONES EN IRN Y M 100, SE PRESENTAN ALGORITMOS HEURISTICOS, BASADOS EN UNA NUEVA REGLA DE ASIGNACION DE LOS PUNTOS DE A A LOS CENTROS DE C, Y SE ESTUDIAN SUS PROPIEDADES. SE REALIZAN ESTUDIOS COMPUTACIONALES PARA N=2, 4, 6, 8 Y 10 Y M=500T, T=L,...,10 QUE PERMITEN COMPARAR LOS DIFERENTES ALGORITMOS PROPUESTOS, Y ESTABLECER CONCLUSIONES EN CUANTO A SU TIEMPO DE COMPUTACION Y CALIDAD DE LA SOLUCION OBTENIDA. PARA K=L, SE OBTIENEN BUENOS RESULTADOS EN TIEMPOS DE COMPUTACION INFERIORES A 15 SEG. EN TODOS LOS CASOS. PARA K L, LOS ALGORITMOS OBTENIDOS SE EJECUTAN CON MENORES TIEMPOS DE COMPUTACION Y PROPORCIONAN MEJORES VALORES OBJETIVO QUE CUANDO SE ASIGNAN LOS PUNTOS A LOS CENTROS MAS CERCANOS, SIENDO LOS TIEMPOS DE COMPUTACION INFERIORES A 10 SEG. EN TODOS LOS CASOS.