Browsing Bergen Open Research Archive by Author "Simonov, Kirill"
Now showing items 16 of 6

Algorithmic Complexity of Clustering and LowRank Approximation Problems
Simonov, Kirill (Doctoral thesis, 20210329)The two most popular unsupervised learning problems are kClustering and LowRank Approximation. Consider a set of n datapoints, in the kClustering problem, the objective is to partition these points into k clusters and ... 
Building large kcores from sparse graphs
Fomin, Fedor; Sagunov, Danil; Simonov, Kirill (Journal article; Peer reviewed, 2020)A popular model to measure network stability is the kcore, that is the maximal induced subgraph in which every vertex has degree at least k. For example, kcores are commonly used to model the unraveling phenomena in ... 
LowRank Binary Matrix Approximation in ColumnSum Norm
Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Simonov, Kirill (Journal article; Peer reviewed, 2020)We consider 𝓁₁Rankr Approximation over {GF}(2), where for a binary m× n matrix 𝐀 and a positive integer constant r, one seeks a binary matrix 𝐁 of rank at most r, minimizing the columnsum norm ‖ 𝐀 𝐁‖₁. We show ... 
Parameterized complexity of PCA
Fomin, Fedor; Golovach, Petr; Simonov, Kirill (Journal article; Peer reviewed, 2020)We discuss some recent progress in the study of Principal Component Analysis (PCA) from the perspective of Parameterized Complexity. 
Parameterized kClustering: Tractability Island
Fomin, Fedor; Golovach, Petr; Simonov, Kirill (Peer reviewed; Journal article, 2019)In kClustering we are given a multiset of n vectors X subset Z^d and a nonnegative number D, and we need to decide whether X can be partitioned into k clusters C_1, ..., C_k such that the cost sum_{i=1}^k min_{c_i in R^d} ... 
Refined Complexity of PCA with Outliers
Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Simonov, Kirill (Conference object; Peer reviewed; Journal article, 2019)Principal component analysis (PCA) is one of the most fundamental procedures in exploratory data analysis and is the basic step in applications ranging from quantitative finance and bioinformatics to image analysis and ...