Article
A discretization result for some optimization problems in framework spaces with polyhedral obstacles and the Manhattan metric
Author/s | Puerto Albandoz, Justo
![]() ![]() ![]() ![]() ![]() ![]() ![]() Rodríguez Madrena, Moisés |
Department | Universidad de Sevilla. Departamento de Estadística e Investigación Operativa |
Publication Date | 2018-07 |
Deposit Date | 2018-11-15 |
Published in |
|
Abstract | 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. |
Funding agencies | Ministerio de Economía y Competitividad (MINECO). España European Commission (EC). Fondo Europeo de Desarrollo Regional (FEDER) |
Project ID. | MTM2016-74983-C02-01
![]() |
Citation | 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. |
Files | Size | Format | View | Description |
---|---|---|---|---|
A discretization result for some ... | 215.3Kb | ![]() | View/ | |