Algorithmics and Computational Complexity Research GroupTalk 19.06.2012

Obtaining Balanced Partitions of Grids using Trees

Andreas Emil Feldmann (Dr., ETH Zürich)

We consider the k-BALANCED PARTITIONING problem, which is defined as
follows. Find the minimum number of edges in a graph that, when cut,
partition the vertices into k (almost) equally sized sets. Amongst
others, the problem derives its importance from the need to distribute
data within a parallel computing architecture. In this setting we are
particularly interested in 2D finite element model (FEM) simulations. We
therefore model the input as a regular quadrilateral tiling of the
plane. More precisely, we focus on solid grid graphs. These are finite
connected subgraphs of the infinite 2D grid without holes.

Trees often help to find solutions to the problem on grid graphs. This
is surprising since trees and grids are very different from a
combinatorial point of view. We show that algorithms for trees help to
improve on existing algorithms for grids, both in the special case when
k=2 (the BISECTION problem) and when k can take arbitrary values.
Additionally we prove that the k-BALANCED PARTITIONING problem
experiences similar hardness on grids and trees.

Date
Speaker
Location
Language
19.06.2012 17:00
Andreas Emil Feldmann
TEL 512
english