2026-08-17T03:45:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5759 2024-03-06T10:37:01Z ddc:004 open_access

Improved Approximation Algorithms for Balanced Partitioning Problems Räcke, Harald Stotz, Richard graph partitioning dynamic programming scheduling We present approximation algorithms for balanced partitioning problems. These problems are notoriously hard and we present new bicriteria approximation algorithms, that approximate the optimal cost and relax the balance constraint. In the first scenario, we consider Min-Max k-Partitioning, the problem of dividing a graph into k equal-sized parts while minimizing the maximum cost of edges cut by a single part. Our approximation algorithm relaxes the size of the parts by (1+epsilon) and approximates the optimal cost by O(log^{1.5}(n) * log(log(n))), for every 0 < epsilon < 1. This is the first nontrivial algorithm for this problem that relaxes the balance constraint by less than 2. In the second scenario, we consider strategies to find a minimum-cost mapping of a graph of processes to a hierarchical network with identical processors at the leaves. This Hierarchical Graph Partitioning problem has been studied recently by Hajiaghayi et al. who presented an (O(log(n)),(1+epsilon)(h+1)) approximation algorithm for constant network heights h. We use spreading metrics to give an improved (O(log(n)),(1+epsilon)h) approximation algorithm that runs in polynomial time for arbitrary network heights. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Harald Räcke and Richard Stotz 2016 Is Part Of LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2016.58 urn:nbn:de:0030-drops-57598 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.58 eng https://creativecommons.org/licenses/by/3.0/legalcode