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.
Document last modified on October 11, 1995