Local Search for Balanced Submodular Clusterings

Narasimhan, Mukund; Bilmes, Jeff A.

Local Search for Balanced Submodular Clusterings

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 981-985.

Abstract

In this paper, we consider the problem of producing balanced clusterings with respect to a submodular objective function. Submodular objective functions occur frequently in many applications, and hence this problem is broadly applicable. We show that the results of Patkar and Narayanan (2003) can be applied to cases when the submodular function is derived from a bipartite object-feature graph, and moreover, in this case we have an efficient flow based algorithm for finding local improvements. We show the effectiveness of this approach by applying it to the clustering of words in language models.

Mukund Narasimhan, and Jeff A. Bilmes. 2007. Local Search for Balanced Submodular Clusterings. In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07. IJCAI, 981–985. https://ijcai.org/proceedings/2007/158

@inproceedings{ijcai2007p158,
  title     = {Local Search for Balanced Submodular Clusterings},
  author    = {Narasimhan, Mukund and Bilmes, Jeff A.},
  booktitle = {Proceedings of the Twentieth International Joint Conference on
               Artificial Intelligence, {IJCAI-07}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Ramon López de Mántaras},
  pages     = {981--985},
  year      = {2007},
  url       = {https://ijcai.org/proceedings/2007/158},
}

TY  - CPAPER
TI  - Local Search for Balanced Submodular Clusterings
AU  - Narasimhan, Mukund
AU  - Bilmes, Jeff A.
T2  - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2007
SP  - 981
EP  - 985
UR  - https://ijcai.org/proceedings/2007/158
ER  -