An Approximation Ratio for Biclustering
| dc.creator | Puolamäki, Kai | |
| dc.creator | Hanhijärvi, Sami | |
| dc.creator | Garriga, Gemma C. | |
| dc.date | 2007-12-17 | |
| dc.date | 2008-08-22 | |
| dc.date.accessioned | 2026-07-07T09:57:35Z | |
| dc.date.available | 2026-07-07T09:57:35Z | |
| dc.description | The problem of biclustering consists of the simultaneous clustering of rows and columns of a matrix such that each of the submatrices induced by a pair of row and column clusters is as uniform as possible. In this paper we approximate the optimal biclustering by applying one-way clustering algorithms independently on the rows and on the columns of the input matrix. We show that such a solution yields a worst-case approximation ratio of 1+sqrt(2) under L1-norm for 0-1 valued matrices, and of 2 under L2-norm for real valued matrices. | |
| dc.description | 9 pages, 2 figures; presentation clarified, replaced to match the version to be published in IPL | |
| dc.identifier | https://arxiv.org/abs/0712.2682 | |
| dc.identifier | http://arxiv.org/abs/0712.2682 | |
| dc.identifier | Information Processing Letters 108 (2008) 45-49 | |
| dc.identifier | doi:10.1016/j.ipl.2008.03.013 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/167394 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Machine Learning | |
| dc.title | An Approximation Ratio for Biclustering | |
| dc.type | text |