Approximation Algorithms for Co-Clustering

Summary: First provable approximation algorithms for co-clustering: simple algorithms achieving constant-factor approximations for simultaneous row/column partitioning of matrices. Also prove co-clustering NP-hard, moving the problem from heuristics to rigorous algorithmic footing. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1460
Venue: PODS
Year: 2008
Pagerank: 4.3648789e-05
Overall Rank: 9,262 | 35.63%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,184	Effective Data Co-Reduction for Multimedia Similarity Search	2011	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
4,188	Clustering via Matrix Powering	2004	PODS	6.3693033e-05
13,623	Programmable Clustering	2006	PODS	-

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,469	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	4.1905499e-05
8,521	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS	4.4893996e-05
1,596	Fast Algorithms for Projected Clustering	1999	SIGMOD	0.00011210688
4,041	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB	6.5048916e-05
4,188	Clustering via Matrix Powering	2004	PODS	6.3693033e-05
1,863	Approximation Algorithms for Clustering Uncertain Data	2008	PODS	0.00010287379
9,753	Minimum Coresets for Maxima Representation of Multidimensional Data	2021	PODS	4.2856385e-05
7,753	ABC: Attributed Bipartite Co-clustering	2022	VLDB	4.6557125e-05
10,928	Improved Approximation Algorithms for Relational Clustering	2024	PODS	4.1905499e-05
3,319	CRD: Fast Co-clustering on Large Datasets Utilizing Sampling-Based Matrix Decomposition	2008	SIGMOD	7.2213704e-05