Polynomial algorithms for partitioning a tree into single‐center subtrees to minimize flat service costs
Open Access
Abstract
This paper deals with the following graph partitioning problem. Consider a connected graph with n nodes, p of which are centers, while the remaining ones are units. For each unit‐center pair there is a fixed service cost and the goal is to find a partition into connected components such that each component contains only one center and the total service cost is minimum. This problem is known to be NP‐hard on general graphs, and here we show that it remains such even if the service cost is monotone and the graph is bipartite. However, in this paper we derive some polynomial time algorithms for trees. For this class of graphs we provide several reformulations of the problem as integer linear programs proving the integrality of the corresponding polyhedra. As a consequence, the tree partitioning problem can be solved in polynomial time either by linear programming or by suitable convex nondifferentiable optimization algorithms. Moreover, we develop a dynamic programming algorithm, whose recursion is based on sequences of minimum weight closure problems, which solves the problem on trees in O(np) time. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008Keywords
This publication has 10 references indexed in Scilit:
- Generalized Bundle MethodsSIAM Journal on Optimization, 2002
- Convex nondifferentiable optimization: A survey focused on the analytic center cutting plane methodOptimization Methods and Software, 2002
- Combinatorial Optimization2001
- On approximating arbitrary metrices by tree metrics1998
- A new algorithm for minimizing convex functions over convex setsMathematical Programming, 1996
- A spanning tree heuristic for regional clusteringCommunications in Statistics - Theory and Methods, 1995
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear ProgramsOperations Research, 1986
- An Algorithmic Approach to Network Location Problems. II: Thep-MediansSIAM Journal on Applied Mathematics, 1979
- An Algorithmic Approach to Network Location Problems. I: Thep-CentersSIAM Journal on Applied Mathematics, 1979
- Optimal Political Districting by Implicit Enumeration TechniquesManagement Science, 1970