Polynomial algorithms for partitioning a tree into single-center subtrees to minimize flat service costs. (English) Zbl 1146.90084
Summary: 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.
MSC:
| 90C39 | Dynamic programming |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C05 | Trees |
Keywords:
tree partitioning; generalized packing problem; \(-1,0,1\)-perfect matrices; maximum closure; dynamic programming; NP-complete problemsReferences:
| [1] | , , , , ”Partitioning a tree into single-center subtrees to minimize flat service costs”, Technical Report, Universidad de Sevilla Dep. to de Estadistíca e Investigación Operativa, (in preparation). · Zbl 1146.90084 |
| [2] | Bartal, Proc of the 30th Ann Symp Foundation Comput Sci pp 161– (1998) |
| [3] | Charikar, Proc 30th Ann Symp Foundation Comput Sci pp 114– (1998) |
| [4] | A short note on graph tree partition problems with assignment or communication objective functions, Internal Report DEI 2001.7 ( 2001), Politecnico di Milano. |
| [5] | Combinatorial Optimization. Packing and Covering, SIAM, CBMS-NSF, Philadelphia, 2001. · Zbl 0972.90059 · doi:10.1137/1.9780898717105 |
| [6] | Frangioni, SIAM J Opt 13 pp 117– (2002) |
| [7] | , Computers and intractability, W. H. Freeman, New York, 1999. |
| [8] | Garfinkel, Manag Sci 16 pp 495– (1970) |
| [9] | Goffin, Opt Methods Software 17 pp 805– (2002) |
| [10] | , , , , Evaluation and optimization of electoral systems, SIAM Monographs on Discrete Mathematics and Applications, SIAM, Society for Industrial and Aplied Mathematics, Philadelphia, 1999. · Zbl 0932.91001 |
| [11] | , Order relations of variables in 0-1 programming, Surveys in combinatorial optimization, , , (Editors), Vol. 31, Annals of Discrete Mathematics, 1987, pp. 83–112. |
| [12] | , Convex analysis and minimization algorithms, Springer, Berlin, 1996. |
| [13] | Kariv, SIAM J Appl Math 37 pp 513– (1979) |
| [14] | Kariv, SIAM J Appl Math 37 pp 539– (1979) |
| [15] | Maravalle, Commun Stat Theory Methods 24 pp 623– (1995) · Zbl 0825.62291 · doi:10.1080/03610929508831512 |
| [16] | Optimal graph partitioning, Atti Giornate di Lavoro AIRO, Urbino 1978, AIRO (Italian Association for Operations Research), Urbino, 1978, pp. 57–73. |
| [17] | , , Duality: Covering and constraining p-center problems on trees, Discrete location theory, (Editors), Wiley, New York, 1990, pp. 349–386. |
| [18] | Tardos, Oper Res 34 pp 250– (1986) |
| [19] | Vaidya, Math Progr 73 pp 291– (1996) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
