Conference proceeding
A Mathematical Model for Load Balancing: ADVANCES IN COMPUTATIONAL SCIENCE
COMPUTATIONAL METHODS IN SCIENCE AND ENGINEERING, VOL 2, Vol.1148, p.824
AIP Conference Proceedings
01/01/2009
DOI: 10.1063/1.3225443
Abstract
We propose a family of semidefinite programming (SDP) relaxations of the problem of graph bisection with preferences. That is, given a graph G = (V, E) we wish to partition the vertices into two disjoint sets V = P-1 boolean OR P-2 so as to minimize the sum of the number of edges cut by the partition and Sigma(i is an element of V)x(i)d(i) where x(i) = +1 if i is an element of P-1 and x(i) = 1 otherwise. The SDP relaxation is related to well-known SDP and spectral relaxations for graph bisection without preferences. The preference vector d can be used to incorporate important information for recursive bisection for data distribution in parallel computers. This relaxation is analogous to an SDP relaxation of graph partitioning related to the spectral relaxation used to obtain the Fiedler vector.
Details
- Title: Subtitle
- A Mathematical Model for Load Balancing: ADVANCES IN COMPUTATIONAL SCIENCE
- Creators
- Suely Oliveira - Univ Iowa, Dept Comp Sci, Iowa City, IA 52242 USATakako Soma - Illinois Coll, Dept Comp Sci, Jacksonville, IL 62650 USA
- Contributors
- T E Simos (Editor)G Maroulis (Editor)
- Resource Type
- Conference proceeding
- Publication Details
- COMPUTATIONAL METHODS IN SCIENCE AND ENGINEERING, VOL 2, Vol.1148, p.824
- Publisher
- Amer Inst Physics
- Series
- AIP Conference Proceedings
- DOI
- 10.1063/1.3225443
- ISSN
- 0094-243X
- eISSN
- 1551-7616
- Number of pages
- 2
- Language
- English
- Date published
- 01/01/2009
- Academic Unit
- Mathematics; Computer Science
- Record Identifier
- 9984410851902771
Metrics
2 Record Views