Campus Event Calendar
Event Entry
New for: D3
What and Who
Graph sparsification for balanced partitioning
Syama Sundar Rangapuram
Fachrichtung Informatik - Saarbrücken
PhD Application Talk
Master Student
AG 1, AG 3, AG 4, AG 5, SWS, RG1, MMCI
Public Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 16 February 2010
13:40
90 Minutes
E1 4
024
Saarbrücken
Abstract
Balanced graph partitioning is the problem of finding an optimal partitioning of a graph according to the specified balance criteria. It is known that balanced partitioning is an NP-hard problem and hence we have to rely on relaxations or heuristics if the problem size is large. The main motivation of this thesis is to solve partitioning problems on large graphs by designing new sparsification techniques. Here, we propose a coarsening scheme that iteratively reduces the problem size by collapsing vertices and edges until
the graph becomes relatively small so that the partitioning problem can solved more satisfactorily with less computation. The important contribution in this work would be provision of certificate of guarantee that the
coarsening step does not disturb the original optimal partitioning; this means that the optimal partitioning of the coarsest graph directly transfers to the optimal partitioning of the original problem. Our method tries to achieve this guarantee by deriving a lower bound on the optimal cut that goes through a given subgraph, before claiming that the subgraphis safe to be coarsened. To find this lower bound, we formulate a modified graph cut problem using spectral relaxation: given a graph G, and a subgraph, S, find the optimal partitioning of G such that the optimal cut goes through S. If we find any other partitioning of G that does not cut S, and whose cut value is smaller than the above bound, then clearly all vertices in S can be collapsed. The modified optimization problem that we derived is non-linear, non-convex and we are currently working on the theoretical proof that we converge to the global optimum. Experimental results suggest that we can solve this problem globally, thus allowing us to provide the guarantee certificate.
the graph becomes relatively small so that the partitioning problem can solved more satisfactorily with less computation. The important contribution in this work would be provision of certificate of guarantee that the
coarsening step does not disturb the original optimal partitioning; this means that the optimal partitioning of the coarsest graph directly transfers to the optimal partitioning of the original problem. Our method tries to achieve this guarantee by deriving a lower bound on the optimal cut that goes through a given subgraph, before claiming that the subgraphis safe to be coarsened. To find this lower bound, we formulate a modified graph cut problem using spectral relaxation: given a graph G, and a subgraph, S, find the optimal partitioning of G such that the optimal cut goes through S. If we find any other partitioning of G that does not cut S, and whose cut value is smaller than the above bound, then clearly all vertices in S can be collapsed. The modified optimization problem that we derived is non-linear, non-convex and we are currently working on the theoretical proof that we converge to the global optimum. Experimental results suggest that we can solve this problem globally, thus allowing us to provide the guarantee certificate.
Contact
IMPRS-CS Office Team
0681 93 25 225
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Stephanie Jörg, 02/12/2010 12:04 -- Created document.