Min-cut clustering |
| |
| Authors: | Ellis L. Johnson Anuj Mehrotra George L. Nemhauser |
| |
| Affiliation: | (1) School of Industrial and Systems Engineering, Georgia Institute of Technology, 30332-0205 Atlanta, GA, USA |
| |
| Abstract: | We describe a decomposition framework and a column generation scheme for solving a min-cut clustering problem. The subproblem to generate additional columns is itself an NP-hard mixed integer programming problem. We discuss strong valid inequalities for the subproblem and describe some efficient solution strategies. Computational results on compiler construction problems are reported.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.This research was supported by NSF grants DMS-8719128 and DDM-9115768, and by an IBM grant to the Computational Optimization Center, Georgia Institute of Technology. |
| |
| Keywords: | Clustering decomposition column generation subproblem optimization valid inequality compiler design |
| 本文献已被 SpringerLink 等数据库收录！ |
|
