scientific article; zbMATH DE number 3871421

From MaRDI portal
Publication:3338296





[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 \textit{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.




Cited in
(21)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3338296)