Blar i Bergen Open Research Archive på forfatter "Simonov, Kirill"

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 ... 
Approximating Long Cycle Above Dirac's Guarantee
Fomin, Fedor; Golovach, Petr; Simonov, Kirill; Sagunov, Danil (Journal article; Peer reviewed, 2023)Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit "natural" guarantees bringing to algorithmic questions whether a better ... 
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 ... 
Building large kcores from sparse graphs
Fomin, Fedor; Sagunov, Danil; Simonov, Kirill (Journal article; Peer reviewed, 2023)A kcore of a graph G is the maximal induced subgraph in which every vertex has degree at least k. In the Edge kCore optimization problem, we are given a graph G and integers k, b and p. The task is to ensure that the ... 
Detours in Directed Graphs
Fomin, Fedor; Golovach, Petr; Lochet, William Alexandre; Sagunov, Danil; Simonov, Kirill; Saurabh, Saket (Journal article; Peer reviewed, 2022)We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Path that we study, called Longest Detour, ... 
Detours in directed graphs
Fomin, Fedor; Golovach, Petr; Lochet, William Alexandre; Sagunov, Danil; Saurabh, Saket; Simonov, Kirill (Journal article; Peer reviewed, 2023)We study two “above guarantee” versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Path that we study, called Longest Detour, ... 
FPT Approximation for Fair MinimumLoad Clustering
Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr; Purohit, Nidhi; Simonov, Kirill (Journal article; Peer reviewed, 2022)In this paper, we consider the MinimumLoad kClustering/Facility Location (MLkC) problem where we are given a set P of n points in a metric space that we have to cluster and an integer k > 0 that denotes the number of ... 
How to find a good explanation for clustering?
Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr; Lochet, William Alexandre; Purohit, Nidhi; Simonov, Kirill (Journal article; Peer reviewed, 2023)kmeans and kmedian clustering are powerful unsupervised machine learning techniques. However, due to complicated dependencies on all the features, it is challenging to interpret the resulting cluster assignments. Moshkovitz, ... 
Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms
Fomin, Fedor; Golovach, Petr; Sagunov, Danil; Simonov, Kirill (Journal article; Peer reviewed, 2022)We discuss recent algorithmic extensions of two classic results of extremal combinatorics about long paths in graphs. First, the theorem of Dirac from 1952 asserts that a 2connected graph G with the minimum vertex degree ... 
Longest Cycle Above ErdösGallai Bound
Fomin, Fedor; Golovach, Petr; Sagunov, Danil; Simonov, Kirill (Journal article; Peer reviewed, 2022)In 1959, Erdős and Gallai proved that every graph G with average vertex degree ad(G) ≥ 2 contains a cycle of length at least ad(G). We provide an algorithm that for k ≥ 0 in time 2^𝒪(k)⋅n^𝒪(1) decides whether a 2connected ... 
Lossy Kernelization of SameSize Clustering
Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr; Purohit, Nidhi; Simonov, Kirill (Journal article; Peer reviewed, 2023)In this work, we study the kmedian clustering problem with an additional equalsize constraint on the clusters from the perspective of parameterized preprocessing. Our main result is the first lossy (2approximate) ... 
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 Feature Selection for Categorical Data Clustering
Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr; Simonov, Kirill (Journal article; Peer reviewed, 2021)We develop new algorithmic methods with provable guarantees for feature selection in regard to categorical data clustering. While feature selection is one of the most common approaches to reduce dimensionality in practice, ... 
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 (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 ... 
Turán's Theorem Through Algorithmic Lens
Fomin, Fedor; Golovach, Petr; Sagunov, Danil; Simonov, Kirill (Journal article; Peer reviewed, 2023)