A Mathematical Model for Load Balancing

被引：0

作者：

Oliveira, Suely ^{[1
]}

Soma, Takako ^{[2
]}

机构：

[1] Univ Iowa, Dept Comp Sci, Iowa City, IA 52242 USA

[2] Illinois Coll, Dept Comp Sci, Jacksonville, IL 62650 USA

来源：

COMPUTATIONAL METHODS IN SCIENCE AND ENGINEERING, VOL 2: ADVANCES IN COMPUTATIONAL SCIENCE | 2009年 / 1148卷

关键词：

semidefinite programming; graph Laplacian; graph partitioning; spectral bisection; SEMIDEFINITE; OPTIMIZATION; RELAXATIONS; ALGORITHM; BISECTION;

D O I：

暂无

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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.

引用

页码：824 / +

页数：2

共 33 条

[1] INTERIOR-POINT METHODS IN SEMIDEFINITE PROGRAMMING WITH APPLICATIONS TO COMBINATORIAL OPTIMIZATION [J].