Tesis doctoral de Lazaro Canovas Martinez
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.
Datos académicos de la tesis doctoral «El problema del k-centro en rn con normas lpb estrictas.«
- Título de la tesis: El problema del k-centro en rn con normas lpb estrictas.
- Autor: Lazaro Canovas Martinez
- Universidad: Murcia
- Fecha de lectura de la tesis: 01/01/1995
Dirección y tribunal
- Director de la tesis
- Blas Pelegrin Pelegrin
- Tribunal
- Presidente del tribunal: Procopio Zoroa Terol
- Miguel Sanchez Garcia (vocal)
- Rafael Infante Macías (vocal)
- José María Ruiz Gomez (vocal)