Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2008-013 (November 06, 2008) Minmax Tree Cover in the Euclidean Space by Seigo Karakawa, Ehab Morsy and Hiroshi Nagamochi

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 $\mathcal{T}$ of $k$ trees of the graph so that the ratio $\alpha$ of $\max_{T\in \mathcal{T}}w(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 $\alpha$ of the corresponding balanced tree partitioning problems. It is known that the best possible value of $\alpha$ is 2 for the general metric space. In this paper, we study the problem in the $d$-dimensional Euclidean space $\mathbb{R}^d$, and break the bound 2 on $\alpha$, showing that $\alpha <2\sqrt{3}-3/2 \fallingdotseq 1.964$ for $d\geq 3$ and $\alpha <(13 + \sqrt{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.