DIMACS Theory of Computing Seminar


Title:

A simple approximation algorithm for multiway separators

Speaker:

Guy Even
Technion

Place:

DIMACS Seminar Room 431, CoRE Building
Busch Campus, Rutgers University

Time:

4:30 PM
Thursday, October 19, 1995

Abstract:

Let G(V,E) denote a graph with edge capacities. A k-sector is a partitioning of the vertices of a graph into k sets of almost equal size. The cost of a k-sector equals the sum of the capacities of the edges connecting vertices that belong to different sets. We present an algorithm that partitions the vertices of a graph into at most k parts, where each part contains at most 2|V|/k vertices. The sum of the capacities of the edges that connect vertices that belong to different parts is at most O(log |V|) times the cost of an optimal k-sector. This result improves over Tragoudas' algorithm in which the approximation factor is O(log k log |V|).

We also present an algorithm that computes a separator whose cost is at most O(log n) times the cost of an optimal bisector. This algorithm does not improve over the Leighton-Rao algorithm, however, the analysis of this algorithm is simpler.

All our algorithms are applicable also to directed graphs and to node-separators.

Joint work with Seffi Naor, Satish Rao, and Baruch Schieber.


dimacs-www@dimacs.rutgers.edu
Document last modified on October 11, 1995