# The Library

### Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut

Tools

Chawla, Shuchi, Gupta, Anupam and Raecke, Harald.
(2008)
*Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut.*
ACM Transactions on Algorithms , Vol.4
(No.2).
ISSN 1549-6325

**Full text not available from this repository.**

Official URL: http://dx.doi.org/10.1145/1361192.1361199

## Abstract

In this article, we study metrics of negative type, which are metrics ( V, d) such that root d is an Euclidean metric; these metrics are thus also known as l(2)-squared metrics. We show how to embed n-point negative-type metrics into Euclidean space l(2) with distortion D = O(log (3/4) n). This embedding result, in turn, implies an O(log (3/4) k)-approximation algorithm for the Sparsest Cut problem with nonuniform demands. Another corollary we obtain is that n-point subsets of l(1) embed into l(2) with distortion O(log (3/4) n).

Item Type: | Journal Article |
---|---|

Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |

Divisions: | Faculty of Science > Computer Science |

Library of Congress Subject Headings (LCSH): | Approximation algorithms, Metric spaces, Embeddings (Mathematics), Graph theory -- Data processing |

Journal or Publication Title: | ACM Transactions on Algorithms |

Publisher: | Association for Computing Machinery, Inc. |

ISSN: | 1549-6325 |

Official Date: | May 2008 |

Volume: | Vol.4 |

Number: | No.2 |

Number of Pages: | 18 |

Identification Number: | 10.1145/1361192.1361199 |

Status: | Peer Reviewed |

Publication Status: | Published |

Access rights to Published version: | Restricted or Subscription Access |

Funder: | National Science Foundation (U.S.) (NSF), Alfred P. Sloan Foundation |

Grant number: | CCR-0122581 (NSF), CCF-0448095 (NSF) |

Version or Related Resource: | Extended version of the paper presented at 16th Annual ACM/SIAM Symposium on Discrete Algorithms, Vancouver, Canada, Jan 23-25, 2005 |

Type of Event: | Other |

References: | ARORA, S., LEE, J., AND NAOR, A. 2005. Euclidean distortion and the sparsest cut. In Proceedings of the |

URI: | http://wrap.warwick.ac.uk/id/eprint/28016 |

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

### Actions (login required)

View Item |

### Downloads

Downloads per month over past year