View PDF HTML (experimental)

Abstract:We study applications of clustering (in particular, the $k$-center clustering problem) in the design of efficient and practical algorithms for computing an approximate and the exact arithmetic matrix product of two 0-1 rectangular matrices with clustered rows or columns, respectively. Our results in part can be regarded as an extension of the clustering-based approach to Boolean square matrix multiplication due to Arslan and Chidri (CSC 2011). First, we provide a simple and efficient deterministic algorithm for approximate matrix product of 0-1 matrices, where the additive error is proportional to the minimum maximum radius in an $\ell$-center clustering of the rows of the first matrix or an $k$-center clustering of the columns of the second matrix. Next, we use the approximation algorithm as a preprocessing after which a query asking for the exact value of an arbitrary entry in the product matrix can be answered in time proportional to the additive error. As a consequence, we obtain a simple deterministic algorithm for the exact matrix product of 0-1 matrices. We also present an improved simple deterministic algorithm for the exact product and in addition, faster analogous randomized algorithms for an approximate and the exact matrix products of 0-1 matrices based on randomized $\ell$ and $k$-center clustering.

Submission history

From: Andrzej Lingas [view email]
[v1] Tue, 25 Mar 2025 13:18:51 UTC (13 KB)
[v2] Wed, 23 Apr 2025 06:18:27 UTC (12 KB)
[v3] Mon, 29 Dec 2025 16:48:31 UTC (30 KB)
[v4] Sat, 4 Jul 2026 06:36:36 UTC (33 KB)