Improved approximation algorithms for balanced partitioning problems

DOI10.4230/LIPICS.STACS.2016.58MaRDI QIDQ4601910zbMATH OpenFDO

Authors Harald Räcke, Richard Stotz

Publication date 24 January 2018

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2016.58

zbMATH Keywords

dynamic programminggraph partitioningscheduling

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Balanced graph partitioning
• Partitioning graphs into balanced components
• Fast Approximate Graph Partitioning Algorithms
• Balanced partitions of trees and applications
• Balanced partitions of trees and applications

Cited in

(12)

• An exact approach for the balanced k-way partitioning problem with weight constraints and its application to sports team realignment
• Fast balanced partitioning is hard even on grids and trees
• Improved Approximation Algorithms for Budgeted Allocations
• Fast balanced partitioning is hard even on grids and trees
• Fast Approximate Graph Partitioning Algorithms
• Partitioning graphs into balanced components
• Balanced Judicious Bipartition is Fixed-Parameter Tractable
• Multiply balanced k-partitioning
• Algorithms for the Balanced Edge Partitioning Problem
• Approximation and parameterized algorithms for balanced connected partition problems
• Balanced graph partitioning
• Approximation algorithm for the balanced 2-connected k-partition problem

This page was built for publication: Improved approximation algorithms for balanced partitioning problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601910)