Improved approximation algorithms for balanced partitioning problems

Harald Räcke, Richard Stotz

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

3 Zitate (Scopus)

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.

OriginalspracheEnglisch
Titel33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016
Redakteure/-innenHeribert Vollmer, Nicolas Ollinger
Herausgeber (Verlag)Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (elektronisch)9783959770019
DOIs
PublikationsstatusVeröffentlicht - 1 Feb. 2016
Veranstaltung33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016 - Orleans, Frankreich
Dauer: 17 Feb. 201620 Feb. 2016

Publikationsreihe

NameLeibniz International Proceedings in Informatics, LIPIcs
Band47
ISSN (Print)1868-8969

Konferenz

Konferenz33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016
Land/GebietFrankreich
OrtOrleans
Zeitraum17/02/1620/02/16

Fingerprint

Untersuchen Sie die Forschungsthemen von „Improved approximation algorithms for balanced partitioning problems“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren