Metric structures in L_1: Dimension, snowflakes, and average distortion

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We study the metric properties of finite subsets of L_1. The analysis of such metrics is central to a number of important algorithmic problems involving the cut structure of weighted graphs, including the Sparsest Cut Problem, one of the most compelling open problems in the field of approximation algorithms. Additionally, many open questions in geometric non-linear functional analysis involve the properties of finite subsets of L_1.
9 pages, 1 figure. To appear in European Journal of Combinatorics. Preliminary version appeared in LATIN '04

Keywords

Metric Geometry, Combinatorics

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/96554

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0407278
 http://arxiv.org/abs/math/0407278
 European J. Combinatorics 26(8): 1180-1190,2005
 doi:10.1016/j.ejc.2004.07.002

Collections

arXiv