2004/06/27 by Konstantin Andreev, Harald Räcke · 1 citation
Computer Science · Engineering · Mathematics · #Approximation algorithm #Binary logarithm #Combinatorics #Computer science #Constant (computer programming) #Discrete mathematics #Generalization #Graph #Graph partition #Interconnection Networks and Systems #Low-power high-performance VLSI design #Mathematics #Time complexity #VLSI and FPGA Design Techniques
paper · doi:10.1145/1007912.1007931
openalex publication_date 2004/06/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
In this paper we consider the problem of (k, υ)-balanced graph partitioning - dividing the vertices of a graph into k almost equal size components (each of size less than υ • n<over>k) so that the capacity of edges between different components is minimized. This problem is a natural generalization of several other problems such as minimum bisection, which is the (2,1)-balanced partitioning problem. We present a bicriteria polynomial time approximation algorithm with an O(log2n)-approximation for any constant υ > 1. For υ = 1 we show that no polytime approximation algorithm can guarantee a finite approximation ratio unless P=NP. Previous work has only considered the (k, υ)-balanced partitioning problem for υ ≥ 2.