Show simple item record

dc.contributor.authorFast, Caleb C.
Hicks, Illya V.
dc.date.accessioned 2017-08-01T16:30:10Z
dc.date.available 2017-08-01T16:30:10Z
dc.date.issued 2017
dc.identifier.citation Fast, Caleb C. and Hicks, Illya V.. "A Branch Decomposition Algorithm for the p-Median Problem." INFORMS Journal on Computing, 29, no. 3 (2017) INFORMS: 474-488. https://doi.org/10.1287/ijoc.2016.0743.
dc.identifier.urihttps://hdl.handle.net/1911/96011
dc.description.abstract In this paper, we use a branch decomposition technique to improve approximations to the p-median problem. Starting from a support graph produced either by a combination of heuristics or by linear programming, we use dynamic programming guided by a branch decomposition of that support graph to find the best p-median solution on the support graph. Our results show that when heuristics are used to build the support graph and the support graph has branchwidth at most 7, our algorithm is able to provide a solution of lower cost than any of the heuristic solutions. When linear programming is used to build the support graph and the support graph has branchwidth at most 7, then our algorithm provides better solutions than popular heuristics and is faster than integer programming. Thus, our algorithm is a useful practical tool when support graphs have branchwidth at most 7.
dc.language.iso eng
dc.publisher INFORMS
dc.rights This is an author's peer-reviewed final manuscript, as accepted by the publisher. The published article is copyrighted by INFORMS.
dc.title A Branch Decomposition Algorithm for the p-Median Problem
dc.type Journal article
dc.citation.journalTitle INFORMS Journal on Computing
dc.subject.keywordFacility Location
p-Median
Branch Decompostion
Dynamic Programming
dc.citation.volumeNumber 29
dc.citation.issueNumber 3
dc.identifier.digital Paper_FINAL
dc.type.dcmi Text
dc.identifier.doihttps://doi.org/10.1287/ijoc.2016.0743
dc.type.publication post-print
dc.citation.firstpage 474
dc.citation.lastpage 488


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record