Metric structures in L1 : dimension, snowflakes, and average distortion
James R. Leea b✉, Manor Mendelc d✉, Assaf Naore f✉
- aComputer Science Division, University of California, Berkeley, Berkeley CA, 94720, USA
- bComputer Science Division, University of California-Berkeley, Berkeley, CA
- cSiebel Center for Computer Science, University of Illinois at Urbana Champaign, Urban IL, 61801, USA
- dSiebel Center for Computer Science, University of Illinois at Urbana Champaign, Urban, IL#TAB#
- eMicrosoft Research, One Microsoft Way, Redmond WA, 98052, USA
- fMicrosoft Research, One Microsoft Way, Redmond, WA
- ✉Corresponding author
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
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. Additionally, many open questions in geometric non-linear functional analysis involve the properties of finite subsets of L 1.
TL;DRThis work studies the metric properties of finite subsets of L 1, which are central to a number of important algorithmic problems involving the cut structure of weighted graphs, including the Sparsest Cut Problem. (Semantic Scholar)