A Branch Decomposition Algorithm for the p -Median Problem

Caleb C. Fast () and Illya V. Hicks ()
Additional contact information
Caleb C. Fast: Department of Computational and Applied Mathematics, Rice University, Houston, Texas 77005
Illya V. Hicks: Department of Computational and Applied Mathematics, Rice University, Houston, Texas 77005

INFORMS Journal on Computing, 2017, vol. 29, issue 3, 474-488

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.

Keywords: facility location; p -median; branch decomposition; dynamic programming (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2016.0743 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:29:y:2017:i:3:p:474-488

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().