A Branch Decomposition Algorithm for the p-Median Problem
提出一种分支分解算法，利用启发式或线性规划构建支撑图，通过动态规划求解p-中位问题。当支撑图分支宽度不超过7时，该算法比常用启发式方法成本更低，且比整数规划更快。
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.