Fulltext

Balanced Partitions of Trees and Applications

Feldmann, Andreas ; Foschini, Luca

In: Algorithmica, 2015, vol. 71, no. 2, p. 354-376

Zum persönliche Liste hinzufügen
    Titel
    • Balanced Partitions of Trees and Applications
    Autor
    • Feldmann, Andreas. Institute of Theoretical Computer Science, ETH Zürich, Zürich, Switzerland
    • Foschini, Luca. Department of Computer Science, U.C. Santa Barbara, Santa Barbara, USA
    Dokumententyp
    • Postprint
    Sprache
    • Englisch
    Veröffentlicht in
    • Algorithmica, 2015, vol. 71, no. 2, p. 354-376. Springer US; http://www.springer-ny.com
    Andere elektronische Ausgabe
    Klassifikation
    • Mathematik
    OAI-PMH-ID
    • oai:doc.rero.ch:332654
    Summary
    We study the problem of finding the minimum number of edges that, when cut, form a partition of the vertices into k sets of equal size. This is called the k-BALANCED PARTITIONING problem. The problem is known to be inapproximable within any finite factor on general graphs, while little is known about restricted graph classes. We show that the k-BALANCED PARTITIONING problem remains APX-hard even when restricted to unweighted tree instances with constant maximum degree. If instead the diameter of the tree is constant we prove that the problem is NP-hard to approximate withinn c , for any constantc<1. If vertex sets are allowed to deviate from being equal-sized by a factor of at most 1+ε, we show that solutions can be computed on weighted trees with cut cost no worse than the minimum attainable when requiring equal-sized sets. This result is then extended to general graphs via decompositions into trees and improves the previously best approximation ratio from O(log1.5(n)/ε 2) [Andreev and Räcke in Theory Comput. Syst. 39(6):929-939, 2006] to O(logn). This also settles the open problem of whether an algorithm exists for which the number of edges cut is independent ofε.