2009年
Minmax Tree Cover in the Euclidean Space
WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS
- ,
- ,
- 巻
- 5431
- 号
- 開始ページ
- 202
- 終了ページ
- 213
- 記述言語
- 英語
- 掲載種別
- 研究論文(国際会議プロシーディングス)
- DOI
- 10.1007/978-3-642-00202-1_18
- 出版者・発行元
- SPRINGER-VERLAG BERLIN
Let G = (V, E) be an edge-weighted graph, and let v)(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 a of max(T is an element of 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 R(d), and break the bound 2 on alpha, showing that alpha < 2 root 3 - 3/2 = 1.964 for d >= 3 and alpha < (13 + root 109)/12 = 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.
- リンク情報
- ID情報
-
- DOI : 10.1007/978-3-642-00202-1_18
- ISSN : 0302-9743
- Web of Science ID : WOS:000264553900018