## Abstract

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/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(log^{2} n)-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.

Original language | English |
---|---|

Pages | 120-124 |

Number of pages | 5 |

DOIs | |

State | Published - 2004 |

Externally published | Yes |

Event | SPAA 2004 - Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures - Barcelona, Spain Duration: 27 Jun 2004 → 30 Jun 2004 |

### Conference

Conference | SPAA 2004 - Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures |
---|---|

Country/Territory | Spain |

City | Barcelona |

Period | 27/06/04 → 30/06/04 |

## Keywords

- Approximation Algorithms
- Bicriteria Approximation
- Graph Partitioning