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.3690661e-05
Overall Rank: 9,257 | 35.61%
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,176	Effective Data Co-Reduction for Multimedia Similarity Search	2011	SIGMOD	4.1945683e-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,187	Clustering via Matrix Powering	2004	PODS	6.3754336e-05
13,610	Programmable Clustering	2006	PODS	-

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,466	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	4.1945683e-05
10,927	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS	4.1945683e-05
1,595	Fast Algorithms for Projected Clustering	1999	SIGMOD	0.00011222442
4,050	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB	6.4953612e-05
4,187	Clustering via Matrix Powering	2004	PODS	6.3754336e-05
1,860	Approximation Algorithms for Clustering Uncertain Data	2008	PODS	0.0001028857
9,772	Minimum Coresets for Maxima Representation of Multidimensional Data	2021	PODS	4.2856106e-05
10,924	Improved Approximation Algorithms for Relational Clustering	2024	PODS	4.1945683e-05
7,752	ABC: Attributed Bipartite Co-clustering	2022	VLDB	4.6601824e-05
3,323	CRD: Fast Co-clustering on Large Datasets Utilizing Sampling-Based Matrix Decomposition	2008	SIGMOD	7.2224696e-05