首页    期刊浏览 2024年11月30日 星期六
登录注册

文章基本信息

  • 标题:Improved Approximation Algorithms for Balanced Partitioning Problems
  • 本地全文:下载
  • 作者:Harald R{\"a}cke ; Richard Stotz
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2016
  • 卷号:47
  • 页码:58:1-58:14
  • DOI:10.4230/LIPIcs.STACS.2016.58
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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.
  • 关键词:graph partitioning; dynamic programming; scheduling
国家哲学社会科学文献中心版权所有