1.7k citations · 1.9k across the 33 of their papers we have counts for
20 papers · 1 filter
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…
A Refined Approximation for Euclidean k-Means
Fabrizio Grandoni, Rafail Ostrovsky, Yuval Rabani +2
In the Euclidean -Means problem we are given a collection of points in an Euclidean space and a positive integer . Our goal is to identify a collection of points…
Min-Sum Clustering (with Outliers)
Sandip Banerjee, Rafail Ostrovsky, Yuval Rabani
We give a constant factor polynomial time pseudo-approximation algorithm for min-sum clustering with or without outliers. The algorithm is allowed to exclude an arbitrarily small c…
Strictly Balancing Matrices in Polynomial Time Using Osborne's Iteration
Rafail Ostrovsky, Yuval Rabani, Arman Yousefi
Osborne's iteration is a method for balancing matrices which is widely used in linear algebra packages, as balancing preserves eigenvalues and stabilizes their numeral…
Matrix Balancing in Lp Norms: A New Analysis of Osborne's Iteration
Rafail Ostrovsky, Yuval Rabani, Arman Yousefi
We study an iterative matrix conditioning algorithm due to Osborne (1960). The goal of the algorithm is to convert a square matrix into a balanced matrix where every row and corres…
Coding for interactive communication correcting insertions and deletions
Mark Braverman, Ran Gelles, Jieming Mao +1
We consider the question of interactive communication, in which two remote parties perform a computation while their communication channel is (adversarially) noisy. We extend here…