Repositorio de producción científica de la Universidad de Sevilla

A discretization result for some optimization problems in framework spaces with polyhedral obstacles and the Manhattan metric

 

Advanced Search
 
Opened Access A discretization result for some optimization problems in framework spaces with polyhedral obstacles and the Manhattan metric
Cites

Show item statistics
Icon
Export to
Author: Puerto Albandoz, Justo
Rodríguez Madrena, Moisés
Department: Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
Date: 2018-07
Published in: Electronic Notes in Discrete Mathematics, 68, 161-165.
Document type: Article
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 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.
Size: 215.3Kb
Format: PDF

URI: https://hdl.handle.net/11441/80198

DOI: 10.1016/j.endm.2018.06.028

See editor´s version

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)