Submodular fractional programming for balanced clustering

Yoshinobu Kawahara, Kiyohito Nagano, Yoshio Okamoto

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)


We address the balanced clustering problem where cluster sizes are regularized with submodular functions. The objective function for balanced clustering is a submodular fractional function, i.e; the ratio of two submodular functions, and thus includes the well-known ratio cuts as special cases. In this paper, we present a novel algorithm for minimizing this objective function (submodular fractional programming) using recent submodular optimization techniques. The main idea is to utilize an algorithm to minimize the difference of two submodular functions, combined with the discrete Newton method. Thus, it can be applied to the objective function involving any submodular functions in both the numerator and the denominator, which enables us to design flexible clustering setups. We also give theoretical analysis on the algorithm, and evaluate the performance through comparative experiments with conventional algorithms by artificial and real datasets.

Original languageEnglish
Pages (from-to)235-243
Number of pages9
JournalPattern Recognition Letters
Issue number2
Publication statusPublished - Jan 15 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence


Dive into the research topics of 'Submodular fractional programming for balanced clustering'. Together they form a unique fingerprint.

Cite this