Zobrazeno 1 - 10
of 107
pro vyhledávání: '"Filtser, Arnold"'
Autor:
Filtser, Arnold, Gadekar, Ameet
The Capacitated Sum of Radii problem involves partitioning a set of points $P$, where each point $p\in P$ has capacity $U_p$, into $k$ clusters that minimize the sum of cluster radii, such that the number of points in the cluster centered at point $p
Externí odkaz:
http://arxiv.org/abs/2409.04984
Autor:
Filtser, Arnold, Friedrich, Tobias, Issac, Davis, Kumar, Nikhil, Le, Hung, Mallek, Nadym, Zeif, Ziena
A $(\beta,\delta,\Delta)$-padded decomposition of an edge-weighted graph $G = (V,E,w)$ is a stochastic decomposition into clusters of diameter at most $\Delta$ such that for every vertex $v\in V$, the probability that $\rm{ball}_G(v,\gamma\Delta)$ is
Externí odkaz:
http://arxiv.org/abs/2407.12230
Autor:
Filtser, Arnold
Given a metric space $(X,d_X)$, a $(\beta,s,\Delta)$-sparse cover is a collection of clusters $\mathcal{C}\subseteq P(X)$ with diameter at most $\Delta$, such that for every point $x\in X$, the ball $B_X(x,\frac\Delta\beta)$ is fully contained in som
Externí odkaz:
http://arxiv.org/abs/2401.14060
Low-distortional metric embeddings are a crucial component in the modern algorithmic toolkit. In an online metric embedding, points arrive sequentially and the goal is to embed them into a simple space irrevocably, while minimizing the distortion. Ou
Externí odkaz:
http://arxiv.org/abs/2310.14078
Autor:
Busch, Costas, Chen, Da Qi, Filtser, Arnold, Hathcock, Daniel, Hershkowitz, D Ellis, Rajaraman, Rajmohan
A spanning tree $T$ of graph $G$ is a $\rho$-approximate universal Steiner tree (UST) for root vertex $r$ if, for any subset of vertices $S$ containing $r$, the cost of the minimal subgraph of $T$ connecting $S$ is within a $\rho$ factor of the minim
Externí odkaz:
http://arxiv.org/abs/2308.01199
A \emph{$\nu$-reliable spanner} of a metric space $(X,d)$, is a (dominating) graph $H$, such that for any possible failure set $B\subseteq X$, there is a set $B^+$ just slightly larger $|B^+|\le(1+\nu)\cdot|B|$, and all distances between pairs in $X\
Externí odkaz:
http://arxiv.org/abs/2307.16612
We introduce and study the communication complexity of computing the inner product of two vectors, where the input is restricted w.r.t. a norm $N$ on the space $\mathbb{R}^n$. Here, Alice and Bob hold two vectors $v,u$ such that $\|v\|_N\le 1$ and $\
Externí odkaz:
http://arxiv.org/abs/2211.13473
Autor:
Filtser, Arnold
Chan, Har-Peled, and Jones [SICOMP 2020] developed locality-sensitive orderings (LSO) for Euclidean space. A $(\tau,\rho)$-LSO is a collection $\Sigma$ of orderings such that for every $x,y\in\mathbb{R}^d$ there is an ordering $\sigma\in\Sigma$, wher
Externí odkaz:
http://arxiv.org/abs/2211.11846
In this paper we initiate the study of expander decompositions of a graph $G=(V, E)$ in the streaming model of computation. The goal is to find a partitioning $\mathcal{C}$ of vertices $V$ such that the subgraphs of $G$ induced by the clusters $C \in
Externí odkaz:
http://arxiv.org/abs/2211.11384
Autor:
Czumaj, Artur, Filtser, Arnold, Jiang, Shaofeng H. -C., Krauthgamer, Robert, Veselý, Pavel, Yang, Mingwei
In Euclidean Uniform Facility Location (UFL), the input is a set of clients in $\mathbb{R}^d$ and the goal is to place facilities to serve them, so as to minimize the total cost of opening facilities plus connecting the clients. We study the setting
Externí odkaz:
http://arxiv.org/abs/2204.02095