Räcke, Harald ;
Stotz, Richard
Improved Approximation Algorithms for Balanced Partitioning Problems
Abstract
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 MinMax kPartitioning, the problem of dividing a graph into k equalsized 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 minimumcost 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.
BibTeX  Entry
@InProceedings{rcke_et_al:LIPIcs:2016:5759,
author = {Harald R{\"a}cke and Richard Stotz},
title = {{Improved Approximation Algorithms for Balanced Partitioning Problems}},
booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages = {58:158:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770019},
ISSN = {18688969},
year = {2016},
volume = {47},
editor = {Nicolas Ollinger and Heribert Vollmer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5759},
URN = {urn:nbn:de:0030drops57598},
doi = {10.4230/LIPIcs.STACS.2016.58},
annote = {Keywords: graph partitioning, dynamic programming, scheduling}
}
2016
Keywords: 

graph partitioning, dynamic programming, scheduling 
Seminar: 

33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Issue date: 

2016 
Date of publication: 

2016 