Abstract
In this paper, we consider the multi-way clustering problem based on graph partitioning models by the Ratio cut and Normalized cut. We formulate the problem using new quadratic models. Spectral relaxations, new semidefinite programming relaxations and linearization techniques are used to solve these problems. It has been shown that our proposed methods can obtain improved solutions. We also adapt our proposed techniques to the bipartite graph partitioning problem for biclustering.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 224-251 |
| Number of pages | 28 |
| Journal | Journal of Combinatorial Optimization |
| Volume | 23 |
| Issue number | 2 |
| DOIs | |
| State | Published - Feb 2012 |
Keywords
- Biclustering
- Clustering
- Graph partitioning
- Normalized cut
- Quadratically constrained programming
- Ratio cut
- Semidefinite programming
- Spectral relaxation
ASJC Scopus subject areas
- Computer Science Applications
- Discrete Mathematics and Combinatorics
- Control and Optimization
- Computational Theory and Mathematics
- Applied Mathematics