Special Issue on Selected Papers from the Third Annual Workshop on Algorithms and Computation (WALCOM 2009)
Minmax Tree Cover in the Euclidean Space
Seigo Karakawa, Ehab Morsy, and Hiroshi Nagamochi
Vol. 15, no. 3, pp. 345-371, 2011. Regular paper.
Abstract Let G=(V,E) be an edge-weighted graph, and let w(H) denote the sum of the weights of the edges in a subgraph H of G. Given a positive integer k, the balanced tree partitioning problem requires to cover all vertices in V by a set T of k trees of the graph so that the ratio α of maxTTw(T) to w(T*)/k is minimized, where T* denotes a minimum spanning tree of G. The problem has been used as a core analysis in designing approximation algorithms for several types of graph partitioning problems over metric spaces, and the performance guarantees depend on the ratio α of the corresponding balanced tree partitioning problems. It is known that the best possible value of α is 2 for the general metric space.
In this paper, we study the problem in the d-dimensional Euclidean space \mathbbRd, and break the bound 2 on α, showing that α < 2√3−3/2 \fallingdotseq 1.964 for d ≥ 3 and α < (13 + √{109})/12 \fallingdotseq 1.953 for d=2. These new results enable us to directly improve the performance guarantees of several existing approximation algorithms for graph partitioning problems if the metric space is an Euclidean space.
Submitted: April 2009.
Reviewed: September 2009.
Revised: July 2010.
Accepted: October 2010.
Final: October 2010.
Published: July 2011.
Communicated by Sandip Das and Ryuhei Uehara
article (PDF)