| |
|
Description: |
Parallel data distribution can be modeled as a Graph Partitioning Problem where we wish to divide a graph into subgraphs with roughly equal number of nodes with a mininum number of edges crossing between the subgraphs. This is a well-known NP-complete problem so heuristics need to be used.
Spectral graph partitioning is a relaxation of the discrete optimization problem. The discrete optimization problem can also be solved approximately by using a Semidefinite Programming (SDP) relaxation. In recursive Graph Partitioning an edge crossing between two sets can not affect the later partitioning of either set.
This problem can be addressed by constructing an optimization problem which includes preferences associated with each vertex. The straightforward relaxation of this model corresponds to an extended eigenvalue problem.
Recently we developed a SDP relaxation for this model and have designed a subspace algorithm for the SDP relaxation.
Area(s):
|
|
Date: |
|
| Start Time: |
16:15 |
|
Speaker: |
Suely Oliveira (University of Iowa, USA)
|
|
Place: |
Room 5.5
|
| Research Groups: |
-Numerical Analysis and Optimization
|
|
See more:
|
<Main>
|
|
