-
Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries
We investigate the problem of exact cluster recovery using oracle querie...
01/31/2021 ∙ by Marco Bressan, et al. ∙
5
∙
share
read it
-
Spectral Clustering Oracles in Sublinear Time
Given a graph G that can be partitioned into k disjoint expanders with o...
01/14/2021 ∙ by Grzegorz Głuch, et al. ∙
0
∙
share
read it
-
Fast and Accurate k-means++ via Rejection Sampling
k-means++ <cit.> is a widely used clustering algorithm that is easy to i...
12/22/2020 ∙ by Vincent Cohen-Addad, et al. ∙
0
∙
share
read it
-
Consistent k-Clustering for General Metrics
Given a stream of points in a metric space, is it possible to maintain a...
11/13/2020 ∙ by Hendrik Fichtenberger, et al. ∙
0
∙
share
read it
-
Secretaries with Advice
The secretary problem is probably the purest model of decision making un...
11/13/2020 ∙ by Paul Dütting, et al. ∙
0
∙
share
read it
-
On Mean Estimation for Heteroscedastic Random Variables
We study the problem of estimating the common mean μ of n independent sy...
10/22/2020 ∙ by Luc Devroye, et al. ∙
0
∙
share
read it
-
InstantEmbedding: Efficient Local Node Representations
In this paper, we introduce InstantEmbedding, an efficient method for ge...
10/14/2020 ∙ by Ştefan Postăvaru, et al. ∙
25
∙
share
read it
-
Sliding Window Algorithms for k-Clustering Problems
The sliding window model of computation captures scenarios in which data...
06/10/2020 ∙ by Michele Borassi, et al. ∙
0
∙
share
read it
-
Fully Dynamic Algorithm for Constrained Submodular Optimization
The task of maximizing a monotone submodular function under a cardinalit...
06/08/2020 ∙ by Silvio Lattanzi, et al. ∙
0
∙
share
read it
-
Exact Recovery of Mangled Clusters with Same-Cluster Queries
We study the problem of recovering distorted clusters in the semi-superv...
06/08/2020 ∙ by Marco Bressan, et al. ∙
0
∙
share
read it
-
Dynamic Algorithms for the Massively Parallel Computation Model
The Massive Parallel Computing (MPC) model gained popularity during the ...
05/22/2019 ∙ by Giuseppe F. Italiano, et al. ∙
0
∙
share
read it
-
MapReduce Meets Fine-Grained Complexity: MapReduce Algorithms for APSP, Matrix Multiplication, 3-SUM, and Beyond
Distributed processing frameworks, such as MapReduce, Hadoop, and Spark ...
05/05/2019 ∙ by MohammadTaghi Hajiaghayi, et al. ∙
0
∙
share
read it
-
Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity
Streaming algorithms are generally judged by the quality of their soluti...
05/02/2019 ∙ by Ehsan Kazemi, et al. ∙
4
∙
share
read it
-
Parallel and Streaming Algorithms for K-Core Decomposition
The k-core decomposition is a fundamental primitive in many machine lear...
08/07/2018 ∙ by Hossein Esfandiari, et al. ∙
0
∙
share
read it
-
Fair Clustering Through Fairlets
We study the question of fair clustering under the disparate impact doc...
02/15/2018 ∙ by Flavio Chierichetti, et al. ∙
0
∙
share
read it
-
ASYMP: Fault-tolerant Mining of Massive Graphs
We present ASYMP, a distributed graph processing system developed for th...
12/28/2017 ∙ by Eduardo Fleury, et al. ∙
0
∙
share
read it
-
One-Shot Coresets: The Case of k-Clustering
Scaling clustering algorithms to massive data sets is a challenging task...
11/27/2017 ∙ by Olivier Bachem, et al. ∙
0
∙
share
read it
-
Local Graph Clustering Beyond Cheeger's Inequality
Motivated by applications of large-scale graph clustering, we study rand...
04/30/2013 ∙ by Zeyuan Allen-Zhu, et al. ∙
0
∙
share
read it
