Show simple item record

dc.creatorPuerto Albandoz, Justoes
dc.creatorRodríguez Chía, Antonio Manueles
dc.creatorTamir, Ariees
dc.creatorPérez Brito, Dionisioes
dc.date.accessioned2016-10-20T10:37:32Z
dc.date.available2016-10-20T10:37:32Z
dc.date.issued2006-07
dc.identifier.citationPuerto Albandoz, J., Rodríguez Chía, A.M., Tamir, A. y Pérez Brito, D. (2006). The bi-criteria doubly weighted center-median path problem on a tree. Networks, 47 (4), 237-247.
dc.identifier.issn0028-3045es
dc.identifier.issn1097-0037es
dc.identifier.urihttp://hdl.handle.net/11441/47847
dc.description.abstractGiven a tree network T with n nodes, let PL be the subset of all discrete paths whose length is bounded above by a prespecified value L. We consider the location of a path-shaped facility P ∈ PL, where customers are represented by the nodes of the tree. We use a bi-criteria model to represent the total transportation cost of the customers to the facility. Each node is associated with a pair of nonnegative weights: the center-weightand the median-weight. In this doubly weighted model, a path P is assigned a pair of values (MAX (P ), SUM (P )),which are, respectively, the maximum center-weighted distance and the sum of the median-weighted distances from P to the nodes of the tree. Viewing PL and the planar set {(MAX (P), SUM (P )) : P ∈ PL} as the decisionspace and the bi-criteria or outcome space respectively,we focus on finding all the nondominated points of the bi-criteria space. We prove that there are at most 2n non-dominated outcomes, even though the total number of efficient paths can be Ω(n2), and they can all be generated in O(n log n) optimal time. We apply this result to solve the cent-dian model, whose objective is a convex combination of the weighted center and weighted median functions. We also solve the restricted models, where the goal is to minimize one of the two functions MAX or SUM, subject to an upper bound on the other one, both withand without a constraint on the length of the path. All these problems are solved in linear time, once the set of non dominated outcomes has been obtained, which in turn, results in an overall complexity of O(n log n). The latter bounds improve upon the best known results by a factor of O(log n).es
dc.description.sponsorshipMinisterio de Ciencia y Tecnologíaes
dc.formatapplication/pdfes
dc.language.isoenges
dc.publisherWileyes
dc.relation.ispartofNetworks, 47 (4), 237-247.
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 Internacional*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.subjectLocation on treeses
dc.subjectBi-criteria locationes
dc.subjectCenter-median pathses
dc.subjectLength constrained pathses
dc.titleThe bi-criteria doubly weighted center-median path problem on a treees
dc.typeinfo:eu-repo/semantics/articlees
dc.type.versioninfo:eu-repo/semantics/submittedVersiones
dc.rights.accessrightsinfo:eu-repo/semantics/openAccesses
dc.contributor.affiliationUniversidad de Sevilla. Departamento de Estadística e Investigación Operativaes
dc.relation.projectIDBFM2001-2378es
dc.relation.projectIDBFM2001-4028es
dc.relation.projectIDBFM2004-0909es
dc.relation.projectIDHA2003-0121es
dc.relation.publisherversionhttp://onlinelibrary.wiley.com/doi/10.1002/net.20112/epdfes
dc.identifier.doi10.1002/net.20112es
dc.contributor.groupUniversidad de Sevilla. FQM331: Métodos y Modelos de la Estadística y la Investigación Operativaes
idus.format.extent29 p.es
dc.journaltitleNetworkses
dc.publication.volumen47es
dc.publication.issue4es
dc.publication.initialPage237es
dc.publication.endPage247es
dc.identifier.idushttps://idus.us.es/xmlui/handle/11441/47847
dc.contributor.funderMinisterio de Ciencia y Tecnología (MCYT). España

FilesSizeFormatViewDescription
The bi-criteria doubly weighted ...262.4KbIcon   [PDF] View/Open  

This item appears in the following collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivatives 4.0 Internacional
Except where otherwise noted, this item's license is described as: Attribution-NonCommercial-NoDerivatives 4.0 Internacional