All reports by Author Yuval Rabani:

__
TR09-121
| 22nd November 2009
__

Zohar Karnin, Yuval Rabani, Amir Shpilka#### Explicit Dimension Reduction and Its Applications

__
TR05-064
| 26th June 2005
__

Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani#### On earthmover distance, metric labeling, and 0-extension

__
TR02-025
| 26th April 2002
__

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani#### Polynomial Time Approximation Schemes for Metric Min-Sum Clustering

Zohar Karnin, Yuval Rabani, Amir Shpilka

We construct a small set of explicit linear transformations mapping $R^n$ to $R^{O(\log n)}$, such that the $L_2$ norm of

any vector in $R^n$ is distorted by at most $1\pm o(1)$ in at

least a fraction of $1 - o(1)$ of the transformations in the set.

Albeit the tradeoff between ...
more >>>

Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani

We study the classification problem {\sc Metric Labeling} and its special case {\sc 0-Extension} in the context of earthmover metrics. Researchers recently proposed using earthmover metrics to get a polynomial time-solvable relaxation of {\sc Metric Labeling}; until now, however, no one knew if the integrality ratio was constant or not, ... more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani

We give polynomial time approximation schemes for the problem

of partitioning an input set of n points into a fixed number

k of clusters so as to minimize the sum over all clusters of

the total pairwise distances in a cluster. Our algorithms work

for arbitrary metric spaces as well ...
more >>>