6 citations · 12 across the 10 of their papers we have counts for
6 papers · 1 filter
Collaborative Top Distribution Identifications with Limited Interaction
Nikolai Karpov, Qin Zhang, Yuan Zhou
We consider the following problem in this paper: given a set of distributions, find the top- ones with the largest means. This problem is also called {\em top- arm identi…
Distributed and Streaming Linear Programming in Low Dimensions
Sepehr Assadi, Nikolai Karpov, Qin Zhang
We study linear programming and general LP-type problems in several big data (streaming and distributed) models. We mainly focus on low dimensional problems in which the number of…
Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
Ivan Bliznets, Nikolai Karpov
Clustering is a well-known and important problem with numerous applications. The graph-based model is one of the typical cluster models. In the graph model, clusters are generally…
An exponential lower bound for cut sparsifiers in planar graphs
Nikolai Karpov, Marcin Pilipczuk, Anna Zych-Pawlewicz
Given an edge-weighted graph with a set of terminals, a mimicking network is a graph with the same set of terminals that exactly preserves the sizes of minimum cuts bet…
Parameterized Complexity of Superstring Problems
Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach +3
In the Shortest Superstring problem we are given a set of strings and integer and the question is to decide whether there is a superstring of le…
Parameterized Complexity of Secluded Connectivity Problems
Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov +1
The Secluded Path problem models a situation where a sensitive information has to be transmitted between a pair of nodes along a path in a network. The measure of the quality of a…