Zobrazeno 1 - 10
of 108
pro vyhledávání: '"Krishnaswamy, Ravishankar"'
We consider the online unrelated-machine load balancing problem with recourse, where the algorithm is allowed to re-assign prior jobs. We give a $(2+\epsilon)$-competitive algorithm for the problem with $O_\epsilon(\log n)$ amortized recourse per job
Externí odkaz:
http://arxiv.org/abs/2211.16216
Autor:
Jaiswal, Shikhar, Krishnaswamy, Ravishankar, Garg, Ankit, Simhadri, Harsha Vardhan, Agrawal, Sheshansh
State-of-the-art algorithms for Approximate Nearest Neighbor Search (ANNS) such as DiskANN, FAISS-IVF, and HNSW build data dependent indices that offer substantially better accuracy and search efficiency over data-agnostic indices by overfitting to t
Externí odkaz:
http://arxiv.org/abs/2211.12850
Autor:
Simhadri, Harsha Vardhan, Williams, George, Aumüller, Martin, Douze, Matthijs, Babenko, Artem, Baranchuk, Dmitry, Chen, Qi, Hosseini, Lucas, Krishnaswamy, Ravishankar, Srinivasa, Gopal, Subramanya, Suhas Jayaram, Wang, Jingdong
Despite the broad range of algorithms for Approximate Nearest Neighbor Search, most empirical evaluations of algorithms have focused on smaller datasets, typically of 1 million points~\citep{Benchmark}. However, deploying recent advances in embedding
Externí odkaz:
http://arxiv.org/abs/2205.03763
Autor:
Gupta, Anupam, Gurunathan, Vijaykrishna, Krishnaswamy, Ravishankar, Kumar, Amit, Singla, Sahil
The vector-balancing problem is a fundamental problem in discrepancy theory: given T vectors in $[-1,1]^n$, find a signing $\sigma(a) \in \{\pm 1\}$ of each vector $a$ to minimize the discrepancy $\| \sum_{a} \sigma(a) \cdot a \|_{\infty}$. This prob
Externí odkaz:
http://arxiv.org/abs/2111.06308
Approximate nearest neighbor search (ANNS) is a fundamental building block in information retrieval with graph-based indices being the current state-of-the-art and widely used in the industry. Recent advances in graph-based indices have made it possi
Externí odkaz:
http://arxiv.org/abs/2105.09613
We consider the online carpooling problem: given $n$ vertices, a sequence of edges arrive over time. When an edge $e_t = (u_t, v_t)$ arrives at time step $t$, the algorithm must orient the edge either as $v_t \rightarrow u_t$ or $u_t \rightarrow v_t$
Externí odkaz:
http://arxiv.org/abs/2007.10545
In the classical Online Metric Matching problem, we are given a metric space with $k$ servers. A collection of clients arrive in an online fashion, and upon arrival, a client should irrevocably be matched to an as-yet-unmatched server. The goal is to
Externí odkaz:
http://arxiv.org/abs/1911.12778
In this paper, we present a new iterative rounding framework for many clustering problems. Using this, we obtain an $(\alpha_1 + \epsilon \leq 7.081 + \epsilon)$-approximation algorithm for $k$-median with outliers, greatly improving upon the large i
Externí odkaz:
http://arxiv.org/abs/1711.01323
In this paper, we study the problem of learning a mixture of Gaussians with streaming data: given a stream of $N$ points in $d$ dimensions generated by an unknown mixture of $k$ spherical Gaussians, the goal is to estimate the model parameters using
Externí odkaz:
http://arxiv.org/abs/1707.02391
In this paper we initiate the study of the heterogeneous capacitated $k$-center problem: given a metric space $X = (F \cup C, d)$, and a collection of capacities. The goal is to open each capacity at a unique facility location in $F$, and also to ass
Externí odkaz:
http://arxiv.org/abs/1611.07414