Show simple item record

dc.contributor.author
Feldmann, Andreas Emil
dc.contributor.author
Foschini, Luca
dc.date.accessioned
2017-11-14T11:40:57Z
dc.date.available
2017-06-10T18:44:10Z
dc.date.available
2017-11-14T11:40:57Z
dc.date.issued
2011
dc.identifier.uri
http://hdl.handle.net/20.500.11850/68887
dc.identifier.doi
10.3929/ethz-a-006906736
dc.description.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.
en_US
dc.language.iso
en
en_US
dc.publisher
ETH, Department of Computer Science
en_US
dc.rights.uri
http://rightsstatements.org/page/InC-NC/1.0/
dc.title
Balanced partitions of trees and applications
en_US
dc.type
Report
dc.rights.license
In Copyright - Non-Commercial Use Permitted
dc.date.published
2011
ethz.journal.title
Technical report
ethz.journal.volume
733
en_US
ethz.size
16 p.
en_US
ethz.code.ddc
0 - Computer science, information & general works::004 - Data processing, computer science
en_US
ethz.notes
Technical Reports D-INFK.
en_US
ethz.identifier.nebis
006906736
ethz.publication.place
Zurich
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science
en_US
ethz.date.deposited
2017-06-10T18:48:09Z
ethz.source
ECOL
ethz.source
ECIT
ethz.identifier.importid
imp593650c1458c687080
ethz.identifier.importid
imp59366b1caf18262029
ethz.ecolpid
eth:5156
ethz.ecitpid
pub:109288
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-07-31T13:46:56Z
ethz.rosetta.lastUpdated
2017-11-14T11:41:05Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&amp;rft_val_fmt=info:ofi/fmt:kev:mtx:journal&amp;rft.atitle=Balanced%20partitions%20of%20trees%20and%20applications&amp;rft.jtitle=Technical%20report&amp;rft.date=2011&amp;rft.volume=733&amp;rft.au=Feldmann,%20Andreas%20Emil&amp;Foschini,%20Luca&amp;rft.genre=report&amp;
 Search via SFX

Files in this item

Thumbnail

Publication type

Show simple item record