Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Yuval Rabani:

TR09-121 | 22nd November 2009
Zohar Karnin, Yuval Rabani, Amir Shpilka

Explicit Dimension Reduction and Its Applications

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 >>>

TR05-064 | 26th June 2005
Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani

On earthmover distance, metric labeling, and 0-extension

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 >>>

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

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 >>>

ISSN 1433-8092 | Imprint