Show simple item record

dc.contributor.authorLeirvåg, Oskar Leonhard Fretheim
dc.date.accessioned2021-12-17T00:47:46Z
dc.date.available2021-12-17T00:47:46Z
dc.date.issued2021-11-22
dc.date.submitted2021-12-16T23:00:07Z
dc.identifier.urihttps://hdl.handle.net/11250/2834804
dc.description.abstractIn the [Fomin et al., 2020b] paper, the authors gave an exact parameterized algorithm for the Binary r-Means clustering problem, parameterized by $k+r$, with the runtime of $2^{\mathcal{O} (\sqrt{rk log(k+r) logr})}*nm$. The problem of Binary r-Means takes as input an $n \times m$ binary matrix \textbf{A} with columns ($\textbf{a}^1,...,\textbf{a}^n$), a positive integer $\textbf{r}$ and a nonnegative integer $\textbf{k}$. The task is then to decide whether there is a positive integer $\textbf{r}\sp{\prime} \leq \textbf{r}$, a partition $\{I_1, ..., I_{r\sp{\prime}}\}$ of $\{1,...,n\}$ and vectors $(\textbf{c}^1,...,\textbf{c}^{r\sp{\prime}}) \in \{0,1\}^m$ such that $\sum_{i = 1}^{r\sp{\prime}} \sum_{j \in I_i} d_H(c^i, a^j) \leq k $, where $d_H$ is the Hamming distance. As the Binary r-Means problem is NP-complete, we cannot expect an algorithm in polynomial time. Therefore its performance as a practical implementation should be evaluated manually in detail, before we make any conclusions about it's viability. An implementation of the algorithm was therefore developed and tested against randomly generated binary matrices, as to measure its performance on a standard desk-top computer. The results show that even a sub-optimal implementation is inconceivably better than a brute force, and viable with small parameters.
dc.language.isoeng
dc.publisherThe University of Bergen
dc.rightsCopyright the Author. All rights reserved
dc.subjectr-means
dc.subjectmatrix
dc.subjectpractical
dc.subjectbinary
dc.subjectfpt
dc.subjectparameter
dc.subjectfixed
dc.subjecttractable
dc.subjectalgorithm
dc.subjectclustering
dc.subjectimplementation
dc.subjectparametrized
dc.titlePractical implementation of a parametrized binary matrix clustering algorithm
dc.typeMaster thesis
dc.date.updated2021-12-16T23:00:07Z
dc.rights.holderCopyright the Author. All rights reserved
dc.description.degreeMasteroppgave i informatikk
dc.description.localcodeINF399
dc.description.localcodeMAMN-PROG
dc.description.localcodeMAMN-INF
dc.subject.nus754199
fs.subjectcodeINF399
fs.unitcode12-12-0


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record