Approximation Algorithms for Min–Max Tree Partition |
| |
Authors: | Nili Guttmann-Beck Refael Hassin |
| |
Institution: | Department of Statistics and Operations Research, Tel Aviv University, Tel Aviv, 69978, Israel |
| |
Abstract: | We consider the problem of partitioning the node set of a graph intopequal sized subsets. The objective is to minimize the maximum length, over these subsets, of a minimum spanning tree. We show that no polynomial algorithm with bounded error ratio can be given for the problem unless P = NP. We present anO(n2) time algorithm for the problem, wherenis the number of nodes in the graph. Assuming that the edge lengths satisfy the triangle inequality, its error ratio is at most 2p − 1. We also present an improved algorithm that obtains as an input a positive integerx. It runs inO(2(p + x)pn2) time, and its error ratio is at most (2 − x/(x + p − 1))p. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|