Name
Abstract | ||
|---|---|---|
This paper investigates the problem of partitioning a complete weighted graph into complete subgraphs, each having the same number of vertices, with the objective of minimizing the sum of edge weights of the resulting subgraphs. This NP-complete problem arises in many applications such as assignment and scheduling-related group partitioning problems and micro-aggregation techniques. In this paper, we present a mathematical programming model and propose a complementary column generation approach to solve the resulting model. A dual based lower bounding feature is also introduced to curtail the notorious tailing-off effects often induced when using column generation methods. Computational results are presented for a wide range of test problems. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.15388/20-INFOR391 | INFORMATICA |
Keywords | DocType | Volume |
graph partitioning, column generation, complementary column generation, mixed-integer programming | Journal | 31 |
Issue | ISSN | Citations |
1 | 0868-4952 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Salem M. Al-Ykoob | 1 | 0 | 0.34 |
| Hanif D. Sherali | 2 | 3403 | 318.40 |