Balanced partitions of trees and applications
OPEN ACCESS
Loading...
Author / Producer
Date
2011
Publication Type
Report
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
We study the k-BALANCED PARTITIONING problem in which the vertices of a graph are to be partitioned into k sets of size at most dn=ke while minimising the cut-size, which is the number of edges connecting vertices in dierent sets. The problem is well studied for general graphs, for which it cannot be approximated within any nite factor in polynomial time. However, little is known about restricted graph classes. We show that for trees k-BALANCED PARTITIONING remains surprisingly hard. In particular, approximating the cut-size is APX-hard even if the maximum degree of the tree is constant. If instead the diameter of the tree is bounded by a constant, we show that it is NP-hard to approximate the cut-size within nc, for any constant c < 1. In the face of the hardness results, we show that allowing near-balanced solutions, in which there are at most (1+")dn=ke vertices in any of the k sets, admits a PTAS for trees. Remarkably, the computed cut-size is no larger than that of an optimal balanced solution. In the nal section of our paper, we harness results on embedding graph metrics into tree metrics to extend our PTAS for trees to general graphs. In addition to being conceptually simpler and easier to analyse, our scheme improves the best factor known on the cut-size of near-balanced solutions from O(log1:5 n="2) [Andreev and R acke TCS 2006] to O(log n), for weighted graphs. This also settles a question posed by Andreev and R acke of whether an algorithm with approximation guarantees on the cut-size independent from " exists.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
733
Pages / Article No.
Publisher
ETH Zurich, Department of Computer Science
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
02150 - Dep. Informatik / Dep. of Computer Science