1 Search Results for "Stotz, Richard"


Document
Improved Approximation Algorithms for Balanced Partitioning Problems

Authors: Harald Räcke and Richard Stotz

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)


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+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.

Cite as

Harald Räcke and Richard Stotz. Improved Approximation Algorithms for Balanced Partitioning Problems. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{racke_et_al:LIPIcs.STACS.2016.58,
  author =	{R\"{a}cke, Harald and Stotz, Richard},
  title =	{{Improved Approximation Algorithms for Balanced Partitioning Problems}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{58:1--58:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.58},
  URN =		{urn:nbn:de:0030-drops-57598},
  doi =		{10.4230/LIPIcs.STACS.2016.58},
  annote =	{Keywords: graph partitioning, dynamic programming, scheduling}
}
  • Refine by Author
  • 1 Räcke, Harald
  • 1 Stotz, Richard

  • Refine by Classification

  • Refine by Keyword
  • 1 dynamic programming
  • 1 graph partitioning
  • 1 scheduling

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail