## Abstract

Graph partitioning problems on graphs with edge capacities and vertex weights are considered. The problems of b-balanced and k-multiway separators are unified with the problem of minimum capacity p-separators. A new and simple O(log n) approximation algorithm is developed for minimum capacity p-separators yielding an O(log n) approximation algorithm for both b-balanced cuts and k-multiway separators. The results are enhanced by presenting a version of the algorithm that obtains an O(log OPT) approximation factor. The techniques involve spreading metrics that allow the minimum capacity p-separator problem to be formulated as an integer program. Generalizations of partitioning problems are also treated.

Original language | English (US) |
---|---|

Pages | 639-648 |

Number of pages | 10 |

State | Published - Jan 1 1997 |

Externally published | Yes |

Event | Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA, USA Duration: Jan 5 1997 → Jan 7 1997 |

### Conference

Conference | Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

City | New Orleans, LA, USA |

Period | 1/5/97 → 1/7/97 |

## All Science Journal Classification (ASJC) codes

- Chemical Health and Safety
- Software
- Safety, Risk, Reliability and Quality
- Discrete Mathematics and Combinatorics