Solving Partition Problems
 |
|
Описание:
The minimum k-partition (MkP) problem is the problem of partitioning the set of vertices of a graph into k disjoint subsets so as to minimize the total weight of the edges joining vertices in the same partition. The main contribution is the design and implementation of a novel iterative clustering heuristic (ICH) based on semide?nite programming to ?nd feasible solutions for the MkP problem. We compare ICH to the hyperplane rounding techniques, and the computational results support the conclusion that ICH consistently provides better feasible solutions for the MkP problem. We use ICH in a branch-and-cut algorithm to provide feasible solutions at each node of the branch-and-bound tree. The branch-and-cut algorithm computes globally optimal solutions for dense graphs with up to 60 vertices, for grid graphs with up to 100 vertices, and for different values of k, providing the best exact approach to date for k>2.Похожие книги
 | Feasibility and Infeasibility in Optimization: Algorithms and Computational Methods Автор: John W. Chinneck Год: 2007 |
| A branch-and-cut algorithm for scheduling of projects with variable-intensity activities Автор: Tamas Kis Год: 2005 |
 | Feasibility and Infeasibility in Optimization: Algorithms and Computational Methods Автор: John W. Chinneck Год: 2007 |
 | Threshold Graphs and Related Topics, Volume 56 (Annals of Discrete Mathematics) Автор: N.V.R. Mahadev, U.N. Peled Год: 1995 |
 | The Grobner Annihilator Graph of a Ring Автор: Trevor McGuire Год: 2010 |
 | Minimum Edge-Ranking Spanning Tree Problem of Series-Parallel Graphs Автор: Ahmed Shamsul Arefin Год: 2010 |