MIN-CUT CLUSTERING

Authors
JOHNSON EL MEHROTRA A NEMHAUSER GL
Citation
El. Johnson et al., MIN-CUT CLUSTERING, Mathematical programming, 62(1), 1993, pp. 133-151
Citations number
16
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics,"Computer Applications & Cybernetics
Journal title
Mathematical programming → ACNP
ISSN journal
00255610
Volume
62
Issue
1
Year of publication
1993
Pages
133 - 151
Database
ISI
SICI code
0025-5610(1993)62:1<133:MC>2.0.ZU;2-Y
Abstract
We describe a decomposition framework and a column generation scheme f or solving a min-cut clustering problem. The subproblem to generate ad ditional columns is itself an NP-hard mixed integer programming proble m. We discuss strong valid inequalities for the subproblem and describ e some efficient solution strategies. Computational results on compile r construction problems are reported.