@inproceedings{623338e8b6bf4bb795f09cb98f9e9751,
title = "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 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 + ε) and approximates the optimal cost by O(log1.5 n log log n), for every 0 < ε < 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(logn), (1 + ε)(h + 1)) approximation algorithm for constant network heights h. We use spreading metrics to give an improved (O(logn), (1 + ε)h) approximation algorithm that runs in polynomial time for arbitrary network heights.",
keywords = "Dynamic programming, Graph Partitioning, Scheduling",
author = "Harald R{\"a}cke and Richard Stotz",
note = "Publisher Copyright: {\textcopyright} Harald R{\"a}cke and Richard Stotz; licensed under Creative Commons License CC-BY.; 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016 ; Conference date: 17-02-2016 Through 20-02-2016",
year = "2016",
month = feb,
day = "1",
doi = "10.4230/LIPIcs.STACS.2016.58",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Heribert Vollmer and Nicolas Ollinger",
booktitle = "33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016",
}