Artículo
A discretization result for some optimization problems in framework spaces with polyhedral obstacles and the Manhattan metric
Autor/es | Puerto Albandoz, Justo
Rodríguez Madrena, Moisés |
Departamento | Universidad de Sevilla. Departamento de Estadística e Investigación Operativa |
Fecha de publicación | 2018-07 |
Fecha de depósito | 2018-11-15 |
Publicado en |
|
Resumen | In this work we consider the shortest path problem and the single facility Weber location problem in any real space of finite dimension where there exist different types of polyhedral obstacles or forbidden regions. These ... In this work we consider the shortest path problem and the single facility Weber location problem in any real space of finite dimension where there exist different types of polyhedral obstacles or forbidden regions. These regions are polyhedral sets and the metric considered in the space is the Manhattan metric. We present a result that reduce these continuous problems into problems in a “add hoc” graph, where the original problems can be solved using elementary techniques of Graph Theory. We show that, fixed the dimension of the space, both the reduction and the resolution can be done in polynomial time. |
Agencias financiadoras | Ministerio de Economía y Competitividad (MINECO). España European Commission (EC). Fondo Europeo de Desarrollo Regional (FEDER) |
Identificador del proyecto | MTM2016-74983-C02-01 |
Cita | Puerto Albandoz, J. y Rodríguez Madrena, M. (2018). A discretization result for some optimization problems in framework spaces with polyhedral obstacles and the Manhattan metric. Electronic Notes in Discrete Mathematics, 68, 161-165. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
A discretization result for some ... | 215.3Kb | [PDF] | Ver/ | |