; TeX output 2006.10.11:1931 nu덍html: html:lnhtml: html:6jXsrc:99aln-journal.texDt G G cmr17Euclidean7tdistortionandtheSparsestCutlύ^ָXQ cmr12SanjeevArora2K cmsy8 xJamesR.Lee2y:iAssafNaor2z1{ src:101aln-journal.tex,"V
cmbx10Abstractǘ*`src:102aln-journal.texK`y
cmr10W*eprovethatevery
b>
cmmi10n-pGointmetricspaceofnegativetypGe(and,inparticular,
everyn- `pGoint#subsetofLٓR cmr71|s)embGedsintoaEuclideanspacewithdistortionOG(s4
!",
cmsy10pUWs4 fe ̍logTnսlogklog en),-aresult`which/Wis/Xtightup/Xtotheiteratedlogarithmfactor.eAsaconsequence,6weobtainthebGestknown`pGolynomial-timeapproximationalgorithmalgorithmfortheSparsestCutproblemwithgeneral`demands.eIfo5theo4demandissuppGortedonasubsetofsizekP,uweachieveo4anapproximationo4ratio`ofUUOG(s4pUWs4 fe ̍logTk8log4logckP).html: html: 3N ff cmbx121LIntros3ductionqsrc:119aln-journal.texK`y
3
cmr10Bi-Lipsc!hitzembMeddingsofnitemetricspaces,5 atopicoriginallystudiedingeometricanalysisand
Banac!hspacetheorye,bMecameanintegralpartoftheoreticalcomputersciencefollo!wingworkofLinial,jLondon,jandCRabino!vichC[html:27 html:
4].JTheypresentedCanalgorithmicv!ersionofaresultofBour-gainq[ html:7 html:y]whic!hshowsthatevery4b>
3
cmmi10n-pMointmetricspaceembMedsintoLz|{Y cmr82uwithdistortionOM(logn).Thisgeometric0viewpMoin!toers0awaytounderstand0theapproximationratiosachieved0bylinearpro-gramming(LP)andsemideniteprogramming(SDP)relaxationsforcutproblems[html:27 html:
4,html:5 html: ]].٧ItsoMonbMecameapparen!tthatfurtherprogressinunderstandingSDPrelaxationsw!ouldinvolveimprovingBourgain'sgeneralbMoundofO(logn)forn-poin!tmetricspacesofnegativetypMe.Feorinstance,theappro!ximationratioachievedbyawell-knownSDPVrelaxationforthegeneralSparsestCutproblemiskno!wntocoincideexactlywiththebMest-possibledistortionbMoundachievdDablefortheembMeddingof n-pMoin!tmetricsofnegativetypMeintoLz1|astrikingconnectionbMetweenpuremathematicsandalgorithmfdesign. src:138aln-journal.texFeurthermOprogressonthesemNproblemsrequirednewinsigh!tsintothemNstructureofmetricspacesof1/negativ!etypMe,Sandthedesignof10moresophisticatedand
exibleembMeddingmethodsfornitemetrics.YECoinciden!tallye,D|signicant$progressw!asmaderecently$onbMoththesefronts.YEArora,D|Raoand(+Veazirani(,[html:4 html:y]pro!ved(+anewstructuraltheoremabMoutmetricspacesofnegativ!etypMe(,andusedit9to:designanOM(5!",
3
cmsy10p p Djlogn)-appro!ximationalgorithmfor9 ':
3
cmti10uniformecpaseoftheSparsestCutproblem.Krauthgamer,ـLee,فMendelandNaor[html:21 html:
4]in!troMducedanewembMeddingmethodcalledmepasureddescpent˹whic!huniedandstrengthenedman!yexistingem!bMeddingtechniques,dandtheyusedittosolv!efanumbMerofopenproblemsintheeld. src:151aln-journal.texThesebreakthroughsindeedresultedinimpro!vedembMeddingsfornegativ!etypMemetrics;IChawla,Gupta,andRfac!ke[html:10 html:
4]usedthestructuraltheoremof[html:4 html:y](spMecicallye,itsstrongerformdueto ff .
L͍Q
-=q% cmsy6a%o cmr9SuppAortedIb9yIDavidandLucilePack|rardIF:ellowshipandNSFIgrantCCR-0205594.
vPrincetonUniversity:. +ߤN cmtt9arora@cs.princeton.eduJ=-=yaSuppAortedSb9yNSFRgrantCCR-0121555andanNSFRGraduateResearchF:ellowship.
ZU.C.Berkeley:.jrl@cs.berkeley.edu-=zaMicrosoftTResearc9h.panaor@microsoft.com #ع1 *nu덍html: html:ln덹LeeD}[html:22 html:
4]),XinconjunctionwithD|measureddescen!ttosho!wthateveryD|n-pMointmetricofD|negativetypMe
em!bMeds]into\Lz2 QawithdistortionOM(logn)32 cmmi8=4
@.Inthepresen!twork,weshowhowone\canachievedistortionOM(p p Djlogn"alog
log"n)."lThisalmostmatc!hesthe35-year-oldlowerbMoundofp
2 p Djlogn'ϾfromEn
oc![html:13 html:
4].qOurmethoMdsc"usetheresultsof[html:4 html:y,html:22 html:VV,html:10 html:VU]essen!tiallyasa\blac!kbMox,"ptogetherwithanenhancemen!tfofthemeasureddescenttechnique. src:164aln-journal.texRecall'uthat'tametricspace(X@<;1d)issaidtobMeofnepgativev type'uif(X@<;1p
2 p Td9)isisometrictoasubsetofOEuclideanspace.Inparticular,aitisOw!ellknownthatLz1˹isOofnegativetypMe.(WeeOalsoremindthereaderthatLz2عisisometricallyequivdDalen!ttoasubsetofLz1.)u(Theparametercz2(X ),pkno!wnastheEuclidepandistortionv,ofX ,istheleastv-distortionwithwhic!hXR%embMedsintoHilbMertv-space,i.e.itisthe&Pminim!um&Qof:m#R
3
cmss10distortion.0t(f-)
=kfkLipSnkf 18kLip
o!ver&Pallbijections&Qf8c:
X,,!Lz2.+The&Pmathematicalin!vestigation
Poftheproblemw!estudyheregoMesbacktotheworkofEn
o[html:13 html:
4],'
whoshowedthattheGEuclideanHdistortionoftheHammingcubMe
ȮdO=
f0;11gdequalsp3I p Td=?6u
3
cmex10p
ܟ? p ' \log$͟2j
Ȯdߨj5e.TheGfollo!wingnaturalfquestionisfolkloreingeometricandfunctionalanalysis.l src:181aln-journal.tex\Isthediscrpeted-dimensionalhypercubethemostnon-Euclidean2dߨ-pointsubsetofLz1?"lsrc:185aln-journal.texA.pMositiv!eFanswertothisquestionwouldimplythatanyn-pMointsubsetofLz1JembMedsinLz2JwithdistortionCOM(p p Djlogn). Infact,motivdDatedCb!yF.John'stheoreminconvexgeometry(see[html:32 html:
4]),JohnsonandLindenstrauss[html:19 html:
4]ask!edin1983whetherev!eryn-pMointmetricspaceem!bMedsintoLz2 IιwithdistortionOM(p p Djlogn).
Here,£theanalogybet!weennitedimensionalnormedspacesandnite|metricspaces}isnotcomplete: Bourgain[ html:7 html:y]hassho!wnthatforanyn-pMoint}metricspaceX ,cz2(X )
=OM(logn),sandfthisfresultisexisten!tiallyoptimal[html:27 html:
4,html:5 html:x].ȰByno!wweunderstandfthatnitemetricspaces(namelyexpandergraphs)canexhibitanisopMerimetricprolewhic!hnonormedspacecanac!hieve,andthisisthereasonforthediscrepancywithJohn'stheorem.Ho!wever,itisknown(see8[html:21 html:
4])8thatsev!eralnaturalrestrictedclassesofmetricsdoadheretotheOM(p p Djlogn)Euclideandistortionsuggestedb!yJohn'stheorem.-Arguablye,forapplicationsintheoreticalcomputersci-ence,
themostimpMortan!trestrictedclassofmetricsarethoseofnegativ!etypMe,
yetimprovementso!verBourgain'stheoremforsuc!hmetricshavelongresistedtheattemptsofmathematiciansandcomputerfscien!tists. src:207aln-journal.texThe2presen!tpapMerisdevotedtoprovingthatuptoiteratedlogarithmicfactors,%theanswerto}theabMo!ve}questionis~positiv!e."Thisyieldsageneraltoolforthe~roundingofcertainclassesofsemi-deniteBprograms.qAsaresult,w!eobtainCthebMest-knownpMolynomialtimealgorithmfortheappro!ximationoftheSparsestCutproblemwithgeneraldemands,iimprovingoverthepreviousbMounds9due8to[html:10 html:
4]andtheprecedingw!orks[html:27 html:
4]and[html:5 html:y](whic!hyieldanOM(logn)appro!ximation).ThispzproblemisdescribMedinSectionp{html:1.1 html:.<Weeno!wstateourmainresult.<Inthecaseofmetricsofnegativ!etypMe(andnotjustLz1 وmetrics),vIitansw!erspMositively(uptoiteratedlogarithms)aw!ell_Rknownconjecture_Sintheoreticalcomputerscienceandmetricgeometry(statedexplicitlyb!yGoMemansfin[html:16 html:
4]).html: html:lF="V
3
cmbx10Theorem21.1. src:223aln-journal.texLpet(X@<;1d)beann-pointmetricspaceofnegativetype. vThenu pcz2(X )
=O!m2fpgf p 嚍logn,nlogflog"^nm``: src:232aln-journal.texRelatedwtork.'Un!til3recentlye,Vtherewaslittle3~solidevidencebMehindtheconjecturethatan!yn-pMoin!tasubset`ofLz1LdembMedsin`Hilbertspacewith`distortionO(p p Djlogn).Inthe`paper[html:23 html:
4],Lee,Mendeland\jNaor\ksho!wthatanyn-pMoint\ksubsetofLz1 nembMeds\kintoHilbMertspacewith\kaverpage^distortionOM(p p Djlogn).Arora,Rao,and*Veazirani[html:4 html:y]+ha!ve*shownthatOM(p p Djlogn)+distortionisachievdDable+usinga #2 nu덍html: html:ln덹dieren!t$notionofaverage#distortion,1whichturnsouttobMemorerelevdDant#forbMoundingtheactual
distortion.AsdescribMedabo!ve,>)combiningtheirresultwiththemeasureddescen!ttechniqueofKrauthgamer,ɵLee,ɴMendelrandNaor[html:21 html:
4],Cha!wla,ɴGupta,andRfac!ker[html:10 html:
4]ha!verrecentlyprovedthatsforsan!yn-pMointmetricspacesXOùofnegativestypMe,}cz2(X )
=O(logn)3=4
@.Itsw!assconjectured[html:29 html:
4,pg.379][thatn-pMoin!tmetricsofnegativetypMe[embed[intoLz1withdistortionOM(1).Recentlye,jKhotandfVishnoi[html:20 html:
4]ha!vefobtainedalo!werfbMoundof
(loglogn),forsomeconstan!tt>
0. src:252aln-journal.texOurresultsalsosuggestthatthedimensionreductionlo!werbMoundofBrinkmanandCharikdDar[html:8 html:y](seeM@alsoMA[html:24 html:
4])istigh!tforcertaindistortions.&Theysho!wthatem!bMeddingcertainn-poin!tMAsubsetsofLz1ݹin!to`dS1ၹwithdistortionDOrequiresthatdn
(1=D