Partitioning, spectra and linear programming.

*(English)*Zbl 0547.05059
Progress in combinatorial optimization, Conf., Waterloo/Ont. 1982, 13-25 (1984).

[For the entire collection see Zbl 0535.00030.]

\(K_ m\) is the complete undirected graph with m nodes and \(a_{rs}\) is a real number assigned to edge (r,s). Call P a partition of the m nodes of \(K_ m\) into subsets \(S_ 1,S_ 2,...,S_ p\) with \(| S_ j| =m_ j\) and suppose \(m_ 1\geq m_ 2\geq...\geq m_ p\). Let \(f(P)=\sum (a_{rs}: r<s\) and r and s are in different subsets \(S_ j)\). Lower bounds on f(P) are derived, based on eigenvalues and vectors of the matrix \(B=A+D\) where \((A)_{rs}=a_{rs}\) (\(r\neq s)\) and \((A)_{rr}=0\), and D is a diagonal matrix chosen so that the sum of all entries of B is 0 (for example \((D)_{rr}=-1/m\sum_{r}\sum_{s\neq r}a_{rs}\) for each r). The problem of minimizing f(P) is an integer programming problem. Several linear programs are proposed as lower bounds to min f(P) and heuristic greedy type algorithms are used to solve these problems. This approach introduces a class of generalized transportation problems which can be solved by a greedy algorithm using the Mong sequence idea. (See A. J. Hoffman [Proc. Symp. Pure Math. 7, 321- 327 (1963; Zbl 0171.178)].) The paper concludes with a discussion of numerical results. The proof of the validity of the greedy algorithm is not included in the paper, for lack of space.

\(K_ m\) is the complete undirected graph with m nodes and \(a_{rs}\) is a real number assigned to edge (r,s). Call P a partition of the m nodes of \(K_ m\) into subsets \(S_ 1,S_ 2,...,S_ p\) with \(| S_ j| =m_ j\) and suppose \(m_ 1\geq m_ 2\geq...\geq m_ p\). Let \(f(P)=\sum (a_{rs}: r<s\) and r and s are in different subsets \(S_ j)\). Lower bounds on f(P) are derived, based on eigenvalues and vectors of the matrix \(B=A+D\) where \((A)_{rs}=a_{rs}\) (\(r\neq s)\) and \((A)_{rr}=0\), and D is a diagonal matrix chosen so that the sum of all entries of B is 0 (for example \((D)_{rr}=-1/m\sum_{r}\sum_{s\neq r}a_{rs}\) for each r). The problem of minimizing f(P) is an integer programming problem. Several linear programs are proposed as lower bounds to min f(P) and heuristic greedy type algorithms are used to solve these problems. This approach introduces a class of generalized transportation problems which can be solved by a greedy algorithm using the Mong sequence idea. (See A. J. Hoffman [Proc. Symp. Pure Math. 7, 321- 327 (1963; Zbl 0171.178)].) The paper concludes with a discussion of numerical results. The proof of the validity of the greedy algorithm is not included in the paper, for lack of space.

Reviewer: L.Kaufmann

##### MSC:

05C99 | Graph theory |

05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |

90B99 | Operations research and management science |