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). doi:10.1145/1361192.1361199 ISSN 1549-6325.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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, Engineering and Medicine > 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 | ||||
Dates: |
|
||||
Volume: | Vol.4 | ||||
Number: | No.2 | ||||
Number of Pages: | 18 | ||||
DOI: | 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 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |