20 citations · 45 across the 23 of their papers we have counts for
19 papers · 1 filter
A Fixed Parameter Sublinear Time Approximation Scheme for Metric Min-Sum Clustering
Karthik C. S., Euiwoong Lee, Yuval Rabani +2
Metric -minsum clustering is a simple, natural, appealing density-based clustering criterion whose computational complexity remains poorly understood, despite the progress achie…
Budget and Profit Approximations for Spanning Tree Interdiction
Rafail Ostrovsky, Yuval Rabani, Yoav Siman Tov
We give polynomial time logarithmic approximation guarantees for the budget minimization, as well as for the profit maximization versions of minimum spanning tree interdiction. In…
New Results on a General Class of Minimum Norm Optimization Problems
Kuowen Chen, Jian Li, Yuval Rabani +1
We study the general norm optimization for combinatorial problems, initiated by Chakrabarty and Swamy (STOC 2019). We propose a general formulation that captures a large class of c…
On Approximability of Min-Sum Clustering
Karthik C. S., Euiwoong Lee, Yuval Rabani +2
The min-sum -clustering problem is to partition an input set into clusters to minimize . Although $\ell_2^2…
The Randomized -Server Conjecture is False!
Sébastien Bubeck, Christian Coester, Yuval Rabani
We prove a few new lower bounds on the randomized competitive ratio for the -server problem and other related problems, resolving some long-standing conjectures. In particular,…
Generalized Unrelated Machine Scheduling Problem
Shichuan Deng, Jian Li, Yuval Rabani
We study the generalized load-balancing (GLB) problem, where we are given jobs, each of which needs to be assigned to one of unrelated machines with processing times $\{p_{…