Approximation Algorithms for Bregman Co-clustering and Tensor Clustering

Details Approximation Algorithms for Bregman Co-clustering and Tensor Clustering Approximation Algorithms for Bregman Co-clustering and Tensor Clustering

2008-12-01

arxiv.org/abs/0812.0389v4

short version in ALT 2009

Computer Science

Data Structures and Algorithms

18 pages; improved metric case

Scientific paper

In the past few years powerful generalizations to the Euclidean k-means problem have been made, such as Bregman clustering [7], co-clustering (i.e., simultaneous clustering of rows and columns of an input matrix) [9,18], and tensor clustering [8,34]. Like k-means, these more general problems also suffer from the NP-hardness of the associated optimization. Researchers have developed approximation algorithms of varying degrees of sophistication for k-means, k-medians, and more recently also for Bregman clustering [2]. However, there seem to be no approximation algorithms for Bregman co- and tensor clustering. In this paper we derive the first (to our knowledge) guaranteed methods for these increasingly important clustering settings. Going beyond Bregman divergences, we also prove an approximation factor for tensor clustering with arbitrary separable metrics. Through extensive experiments we evaluate the characteristics of our method, and show that it also has practical impact.

Affiliated with

Also associated with

No associations

Rating

Approximation Algorithms for Bregman Co-clustering and Tensor Clustering does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximation Algorithms for Bregman Co-clustering and Tensor Clustering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation Algorithms for Bregman Co-clustering and Tensor Clustering will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-718424