Zobrazeno 1 - 10
of 298
pro vyhledávání: '"KRAUTHGAMER, ROBERT"'
The Johnson-Lindenstrauss (JL) Lemma introduced the concept of dimension reduction via a random linear map, which has become a fundamental technique in many computational settings. For a set of $n$ points in $\mathbb{R}^d$ and any fixed $\epsilon>0$,
Externí odkaz:
http://arxiv.org/abs/2312.01391
Autor:
Kenneth, Yotam, Krauthgamer, Robert
In cut sparsification, all cuts of a hypergraph $H=(V,E,w)$ are approximated within $1\pm\epsilon$ factor by a small hypergraph $H'$. This widely applied method was generalized recently to a setting where the cost of cutting each hyperedge $e$ is pro
Externí odkaz:
http://arxiv.org/abs/2307.09110
We design new parallel algorithms for clustering in high-dimensional Euclidean spaces. These algorithms run in the Massively Parallel Computation (MPC) model, and are fully scalable, meaning that the local memory in each machine may be $n^{\sigma}$ f
Externí odkaz:
http://arxiv.org/abs/2307.07848
Many streaming algorithms provide only a high-probability relative approximation. These two relaxations, of allowing approximation and randomization, seem necessary -- for many streaming problems, both relaxations must be employed simultaneously, to
Externí odkaz:
http://arxiv.org/abs/2303.16287
We study the classical metric $k$-median clustering problem over a set of input rankings (i.e., permutations), which has myriad applications, from social-choice theory to web search and databases. A folklore algorithm provides a $2$-approximate solut
Externí odkaz:
http://arxiv.org/abs/2212.01821
The edit distance between strings classically assigns unit cost to every character insertion, deletion, and substitution, whereas the Hamming distance only allows substitutions. In many real-life scenarios, insertions and deletions (abbreviated indel
Externí odkaz:
http://arxiv.org/abs/2211.12496
Max-Cut is a fundamental problem that has been studied extensively in various settings. We design an algorithm for Euclidean Max-Cut, where the input is a set of points in $\mathbb{R}^d$, in the model of dynamic geometric streams, where the input $X\
Externí odkaz:
http://arxiv.org/abs/2211.05293
We study distributed schemes for high-dimensional sparse linear regression, based on orthogonal matching pursuit (OMP). Such schemes are particularly suited for settings where a central fusion center is connected to end machines, that have both compu
Externí odkaz:
http://arxiv.org/abs/2209.07230
Autor:
Braverman, Vladimir, Cohen-Addad, Vincent, Jiang, Shaofeng H. -C., Krauthgamer, Robert, Schwiegelshohn, Chris, Toftrup, Mads Bech, Wu, Xuan
Motivated by practical generalizations of the classic $k$-median and $k$-means objectives, such as clustering with size constraints, fair clustering, and Wasserstein barycenter, we introduce a meta-theorem for designing coresets for constrained-clust
Externí odkaz:
http://arxiv.org/abs/2209.01901
Autor:
Krauthgamer, Robert, Mosenzon, Ron
Given a large edge-capacitated network $G$ and a subset of $k$ vertices called terminals, an (exact) flow sparsifier is a small network $G'$ that preserves (exactly) all multicommodity flows that can be routed between the terminals. Flow sparsifiers
Externí odkaz:
http://arxiv.org/abs/2207.07363