scientific article; zbMATH DE number 3871421
[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.
- Algorithms for graph partitioning problems by means of eigenspace relaxations
- scientific article; zbMATH DE number 736319
- Constructive Heuristics and Lower Bounds for Graph Partitioning Based on a Principal-Components Approximation
- Graph partitioning using linear and semidefinite programming
- A computational study of graph partitioning
- Combinatorial and spectral aspects of nearest neighbor graphs in doubling dimensional and nearly-Euclidean spaces
- Optimal partitions having disjoint convex and conic hulls
- A quadratically convergent local algorithm on minimizing sums of the largest eigenvalues of a symmetric matrix
- On some difficult linear programs coming from set partitioning
- Spectral methods for graph bisection problems.
- Algorithms for graph partitioning problems by means of eigenspace relaxations
- Linear-shaped partition problems
- New results on the completion time variance minimization
- A projection technique for partitioning the nodes of a graph
- Efficient algorithm for optimizing spectral partitions
- Constructive Heuristics and Lower Bounds for Graph Partitioning Based on a Principal-Components Approximation
- Lower bounds to the graph partitioning problem through generalized linear programming and network flows
- scientific article; zbMATH DE number 736319 (Why is no real title available?)
- scientific article; zbMATH DE number 1416066 (Why is no real title available?)
- On Laplacian spectra of parametric families of closely connected networks with application to cooperative control
- A new Lagrangian net algorithm for solving max-bisection problems
- Constrained partitioning problems
- Algorithms for minclique scheduling problems
- Enumeration of the partitions with minimum diameter
- Optimizing connected components graph partitioning with minimum size constraints using integer programming and spectral clustering techniques
- Spectral partitioning works: planar graphs and finite element meshes
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)