(original) (raw)

%!PS-Adobe-2.0 %%Creator: dvipsk 5.58f Copyright 1986, 1994 Radical Eye Software %%Title: metsff.dvi %%Pages: 12 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%EndComments %DVIPSCommandLine: dvips metsff %DVIPSParameters: dpi=300, comments removed %DVIPSSource: TeX output 2000.06.21:1509 %%BeginProcSet: tex.pro /TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N /X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72 mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1} ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[matrix currentmatrix{dup dup round sub abs 0.00001 lt{round}if} forall round exch round exch]setmatrix}N /@landscape{/isls true N}B /@manualfeed{statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{ /nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{ /sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0] N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{ 128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 sub]{ch-image}imagemask restore}B /D{/cc X dup type /stringtype ne{]} if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{ cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin 0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore userdict /eop-hook known{eop-hook}if showpage}N /@start{userdict /start-hook known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X /IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for 65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0 0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V {}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7 getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false} ifelse}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale rulex ruley false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave newpath transform round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail {dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail}B /c{-4 M} B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{3 M}B /k{ 4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{ p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{3 2 roll p a}B /bos{/SS save N}B /eos{SS restore}B end %%EndProcSet TeXDict begin 40258431 52099146 1000 300 300 (metsff.dvi) @start /Fa 1 51 df<7FFFFF80FFFFFF80C0000180C0000180C0000180C0000180C000 0180C0000180C0000180C0000180C0000180C0000180C0000180C0000180C0000180C000 0180C0000180C0000180C0000180C0000180C0000180C0000180C0000180FFFFFF807FFF FF8019197C9B22>50 D E /Fb 1 108 df<003C000007FC000007FC0000007C00000078 000000780000007800000078000000F0000000F0000000F0000000F0000001E0000001E0 000001E0000001E0000003C00F0003C0308003C0438003C087C007810F8007820F800784 0700078800000F1000000F2000000FC000000FC000001E7800001E1E00001E0F00001E07 80003C0780003C0781003C0781003C07810078070200780702007807020078038400F003 88006000F0001A2A7DA91E>107 D E /Fc 1 50 df<00200000E00001E0000FE000FFE0 00F1E00001E00001E00001E00001E00001E00001E00001E00001E00001E00001E00001E0 0001E00001E00001E00001E00001E00001E00001E00001E00001E00001E00001E00001E0 0001E00001E00001E00001E00001E00001E00001E00001E00003F000FFFFC0FFFFC01228 7BA71D>49 D E /Fd 1 1 df0 D E /Fe 3 113 df<01F006001C00380070007000FFC0E000E000E000E000E0006000300818 300FC00D107F8F10>15 D<0004000C00180018001800300030003000600060006000C000 C000C00180018001800300030003000600060006000C000C000C00180018001800300030 003000600060006000C000C0000E257E9B13>61 D<07078005984009E06009C07009C030 09C0700380700380700380700380600700E00700C00701C00703800E86000E7C000E0000 0E00001C00001C00001C00001C0000FF00001417828F13>112 D E /Ff 47 122 df<000FE000007FF80000F81C0001E07C0003E07C0007C07C0007C07C00 07C0380007C0000007C0000007C0000007C1FE00FFFFFE00FFFFFE0007C03E0007C03E00 07C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007C03E00 07C03E0007C03E0007C03E0007C03E0007C03E003FF9FFC03FF9FFC01A20809F1D>12 D<0030006000C00180038007000F000E001E001C003C003C0038007800780078007800F8 00F000F000F000F000F000F000F000F000F000F800780078007800780038003C003C001C 001E000E000F0007000380018000C0006000300C2D7CA114>40 DI45 D<387CFEFEFE7C3807077C860F>I<0000600000E00000E00001C00001C0000380000380 000380000700000700000700000E00000E00001C00001C00001C00003800003800003800 00700000700000E00000E00000E00001C00001C000038000038000038000070000070000 0700000E00000E00001C00001C00001C0000380000380000380000700000700000E00000 E00000C00000132D7DA11A>I<00700000F00007F000FFF000F9F00001F00001F00001F0 0001F00001F00001F00001F00001F00001F00001F00001F00001F00001F00001F00001F0 0001F00001F00001F00001F00001F00001F00001F0007FFFC07FFFC0121D7D9C1A>49 D<03FC001FFF80381FC07C07E0FE03F0FE03F0FE03F8FE01F87C01F83801F80003F80003 F00003F00007E0000FC0000F00001E00003C0000700000E00001C0180380180600180C00 381FFFF03FFFF07FFFF0FFFFF0FFFFF0151D7E9C1A>I<03FC000FFF801C0FC03C07E07E 03F07E03F07E03F07E07F03C07E00007E0000FC0003F8003FE0003FC00000F800007C000 03E00003F00003F83803F87C03F8FE03F8FE03F8FE03F0FC03F07807E03C0FC01FFF8003 FC00151D7E9C1A>I<0001C00003C00007C00007C0000FC0001FC0003BC00073C00063C0 00C3C00183C00383C00703C00E03C00C03C01803C03803C07003C0E003C0FFFFFEFFFFFE 0007C00007C00007C00007C00007C00007C000FFFE00FFFE171D7F9C1A>I<1C00E01FFF E01FFFC01FFF801FFF001FFC001FC00018000018000018000018000019FE001FFF801E07 C01803E01001F00001F00001F80001F87801F8FC01F8FC01F8FC01F8FC01F07803F07003 E03C0FC00FFF0003FC00151D7E9C1A>I<387CFEFEFE7C38000000000000387CFEFEFE7C 3807147C930F>58 D<0000E000000000E000000001F000000001F000000001F000000003 F800000003F800000006FC00000006FC0000000EFE0000000C7E0000000C7E000000183F 000000183F000000303F800000301F800000701FC00000600FC00000600FC00000C007E0 0000FFFFE00001FFFFF000018003F000038003F800030001F800030001F800060000FC00 060000FC000E0000FE00FFE00FFFE0FFE00FFFE0231F7E9E28>65 D<0007FC02003FFF0E00FE03DE03F000FE07E0003E0FC0001E1F80001E3F00000E3F0000 0E7F0000067E0000067E000006FE000000FE000000FE000000FE000000FE000000FE0000 00FE0000007E0000007E0000067F0000063F0000063F00000C1F80000C0FC0001807E000 3803F0007000FE01C0003FFF800007FC001F1F7D9E26>67 DI70 D76 DI<001FF80000FFFF0001F81F8007E007E00FC003F01F8001F81F0000F83F0000FC7F00 00FE7E00007E7E00007EFE00007FFE00007FFE00007FFE00007FFE00007FFE00007FFE00 007FFE00007FFE00007F7E00007E7F0000FE7F0000FE3F0000FC3F8001FC1F8001F80FC0 03F007E007E001F81F8000FFFF00001FF800201F7D9E27>79 DI82 D<03FC080FFF381E03F83800F8700078700038F00038F00018F00018F80000FC00007FC0 007FFE003FFF801FFFC00FFFE007FFF000FFF80007F80000FC00007C00003CC0003CC000 3CC0003CE00038E00078F80070FE01E0EFFFC081FF00161F7D9E1D>I<7FFFFFFC7FFFFF FC7C07E07C7007E01C6007E00C6007E00CE007E00EC007E006C007E006C007E006C007E0 060007E0000007E0000007E0000007E0000007E0000007E0000007E0000007E0000007E0 000007E0000007E0000007E0000007E0000007E0000007E0000007E0000007E00003FFFF C003FFFFC01F1E7E9D24>I<07FC001FFF803F07C03F03E03F01F03F01F00C01F00001F0 003FF007FDF01F81F03E01F07C01F0F801F0F801F0F801F0FC02F07E0CF03FF87E0FE03E 17147F9319>97 DI<01FE0007FF801F0FC03E0FC03E0FC07C0FC07C0300FC0000FC0000FC0000FC0000 FC0000FC00007C00007E00003E00603F00C01F81C007FF0001FC0013147E9317>I<0007 F80007F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F801F8 F807FEF81F83F83E01F87E00F87C00F87C00F8FC00F8FC00F8FC00F8FC00F8FC00F8FC00 F87C00F87C00F87E00F83E01F81F07F80FFEFF03F8FF18207E9F1D>I<01FE0007FF800F 83C01E01E03E00F07C00F07C00F8FC00F8FFFFF8FFFFF8FC0000FC0000FC00007C00007C 00003E00181E00180F807007FFE000FF8015147F9318>I<003F8000FFC003E3E007C7E0 0787E00F87E00F83C00F80000F80000F80000F80000F8000FFFC00FFFC000F80000F8000 0F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F8000 0F80000F80007FF8007FF80013207F9F10>I<03FC3C0FFFFE1E079E3C03DE7C03E07C03 E07C03E07C03E07C03E03C03C01E07801FFF0013FC003000003000003800003FFF801FFF F00FFFF81FFFFC78007C70003EF0001EF0001EF0001E78003C78003C3F01F80FFFE001FF 00171E7F931A>II<1C003E007F007F007F003E001C00000000000000000000000000FF00FF001F001F 001F001F001F001F001F001F001F001F001F001F001F001F001F001F00FFE0FFE00B217E A00E>I107 DI< FE0FE03F80FE1FF07FC01E70F9C3E01E407D01F01E807E01F01F807E01F01F007C01F01F 007C01F01F007C01F01F007C01F01F007C01F01F007C01F01F007C01F01F007C01F01F00 7C01F01F007C01F01F007C01F01F007C01F0FFE3FF8FFEFFE3FF8FFE27147D932C>II<01FF0007FFC0 1F83F03E00F83E00F87C007C7C007CFC007EFC007EFC007EFC007EFC007EFC007E7C007C 7C007C3E00F83E00F81F83F007FFC001FF0017147F931A>II<01F81807FE381F87783F01F83E01F87E00F87C00F8FC00F8FC 00F8FC00F8FC00F8FC00F8FC00F87C00F87E00F87E00F83F01F81F87F80FFEF803F8F800 00F80000F80000F80000F80000F80000F80000F80007FF0007FF181D7E931C>II<0FE63FFE701E600E E006E006F800FFC07FF83FFC1FFE03FE001FC007C007E007F006F81EFFFCC7F010147E93 15>I<0300030003000300070007000F000F003F00FFFCFFFC1F001F001F001F001F001F 001F001F001F001F001F061F061F061F061F060F8C07F803F00F1D7F9C14>IIIIII E /Fg 40 123 df<1C3C3C3C3C040408081020204080060E7D840E>44 D<7FF0FFE07FE00C037D8A10>I<70F8F8F0E005057B840E>I<0000020000000600000006 0000000E0000001E0000001E0000003F0000002F0000004F000000CF0000008F0000010F 0000010F0000020F0000020F0000040F0000080F0000080F0000100F8000100780002007 80003FFF8000400780008007800080078001000780010007800200078006000780040007 801E0007C0FF807FF81D207E9F22>65 D<01FFFFC0001E00F0001E0078001E0038001E00 3C003C003C003C003C003C003C003C003C0078007800780078007800F0007801E000F007 8000FFFE0000F00F8000F003C001E001C001E001E001E001E001E001E003C001E003C001 E003C001E003C001C0078003C00780078007800F0007801E000F007C00FFFFE0001E1F7D 9E20>I<0000FE0200078186001C004C0038003C0060003C00C0001C01C0001803800018 070000180F0000181E0000101E0000103C0000003C000000780000007800000078000000 78000000F0000000F0000000F0000000F0000000F0000080700000807000008070000100 3800010038000200180004000C001800060020000381C00000FE00001F217A9F21>I<00 FFFF80001E00E0001E0070001E0038001E001C003C001C003C000E003C000E003C000E00 78000E0078000E0078000E0078000E00F0001E00F0001E00F0001E00F0001E01E0003C01 E0003C01E0003C01E0007803C0007003C0007003C000E003C001C0078003C00780038007 800E0007801C000F007000FFFFC0001F1F7D9E22>I<01FFFFFC001E0038001E0018001E 0008001E0008003C0008003C0008003C0008003C00080078001000780800007808000078 080000F0100000F0300000FFF00000F0300001E0200001E0200001E0200001E0200003C0 000003C0000003C0000003C00000078000000780000007800000078000000F800000FFF8 00001E1F7D9E1E>70 D<01FFF0001F00001E00001E00001E00003C00003C00003C00003C 0000780000780000780000780000F00000F00000F00000F00001E00001E00001E00001E0 0003C00003C00003C00003C0000780000780000780000780000F8000FFF000141F7D9E12 >73 D<000FFF8000007C000000780000007800000078000000F0000000F0000000F00000 00F0000001E0000001E0000001E0000001E0000003C0000003C0000003C0000003C00000 078000000780000007800000078000000F0000000F0000300F0000780F0000F81E0000F8 1E0000F03C0000803800004070000020E000001F80000019207D9E18>I<01FFF800001F 0000001E0000001E0000001E0000003C0000003C0000003C0000003C0000007800000078 0000007800000078000000F0000000F0000000F0000000F0000001E0000001E0000001E0 000001E0008003C0010003C0010003C0030003C00200078006000780060007800C000780 1C000F007800FFFFF800191F7D9E1D>76 D<01FE00007FC0001E0000FC00001E0000F800 00170001780000170001780000270002F00000270004F00000270004F00000270008F000 00470009E00000470011E00000470021E00000470021E00000870043C00000838043C000 00838083C00000838083C000010381078000010382078000010382078000010384078000 0203840F00000203880F00000203900F00000203900F00000401E01E00000401E01E0000 0401C01E00000C01801E00001C01803E0000FF8103FFC0002A1F7D9E29>I<01FFFF8000 1E00E0001E0070001E0038001E003C003C003C003C003C003C003C003C003C0078007800 780078007800F0007800E000F003C000F00F0000FFFC0000F0000001E0000001E0000001 E0000001E0000003C0000003C0000003C0000003C0000007800000078000000780000007 8000000F800000FFF000001E1F7D9E1F>80 D<00FFFF00001E03C0001E00E0001E007000 1E0078003C0078003C0078003C0078003C0078007800F0007800F0007801E0007801C000 F0070000F01E0000FFF00000F01C0001E00E0001E00F0001E0070001E0078003C00F0003 C00F0003C00F0003C00F0007801E0007801E0807801E0807801E100F800E10FFF00E2000 0003C01D207D9E21>82 D<0007E040001C18C0003005800060038000C0038001C0018001 8001000380010003800100038001000380000003C0000003C0000003F8000001FF800001 FFE000007FF000001FF0000001F800000078000000780000003800000038002000380020 0038002000300060007000600060006000E0007000C000E8038000C606000081F800001A 217D9F1A>I<0FFFFFFC1E03C0381803C0181003C0082003C00820078008600780084007 800840078008800F0010000F0000000F0000000F0000001E0000001E0000001E0000001E 0000003C0000003C0000003C0000003C00000078000000780000007800000078000000F0 000000F0000000F0000000F0000001F000007FFF80001E1F799E21>I<00F1800389C007 07800E03801C03803C0380380700780700780700780700F00E00F00E00F00E00F00E20F0 1C40F01C40703C40705C40308C800F070013147C9317>97 D<07803F8007000700070007 000E000E000E000E001C001C001CF01D0C3A0E3C0E380F380F700F700F700F700FE01EE0 1EE01EE01CE03CE038607060E031C01F0010207B9F15>I<007E0001C1000300800E0780 1E07801C07003C0200780000780000780000F00000F00000F00000F00000F00000700100 70020030040018380007C00011147C9315>I<0000780003F80000700000700000700000 700000E00000E00000E00000E00001C00001C000F1C00389C00707800E03801C03803C03 80380700780700780700780700F00E00F00E00F00E00F00E20F01C40F01C40703C40705C 40308C800F070015207C9F17>I<007C01C207010E011C013C013802780C7BF07C00F000 F000F000F0007000700170023804183807C010147C9315>I<00007800019C00033C0003 3C000718000700000700000E00000E00000E00000E00000E0000FFE0001C00001C00001C 00001C0000380000380000380000380000380000700000700000700000700000700000E0 0000E00000E00000E00000E00001C00001C00001C0000180003180007B0000F300006600 003C00001629829F0E>I<001E3000713800E0F001C0700380700780700700E00F00E00F 00E00F00E01E01C01E01C01E01C01E01C01E03801E03800E07800E0B8006170001E70000 0700000700000E00000E00300E00781C00F038006070003FC000151D7F9315>I<01E000 0FE00001C00001C00001C00001C000038000038000038000038000070000070000071E00 0763000E81800F01C00E01C00E01C01C03801C03801C03801C0380380700380700380700 380E10700E20700E20701C20700C40E00C8060070014207D9F17>I<00C001E001E001C0 00000000000000000000000000000E001300230043804700470087000E000E000E001C00 1C001C003840388038807080310032001C000B1F7C9E0E>I<01E0000FE00001C00001C0 0001C00001C0000380000380000380000380000700000700000703C00704200E08E00E11 E00E21E00E40C01C80001D00001E00001FC00038E0003870003870003838407070807070 80707080703100E03100601E0013207D9F15>107 D<03C01FC003800380038003800700 0700070007000E000E000E000E001C001C001C001C003800380038003800700070007000 7100E200E200E200E200640038000A207C9F0C>I<1C0F80F0002630C318004740640C00 4780680E004700700E004700700E008E00E01C000E00E01C000E00E01C000E00E01C001C 01C038001C01C038001C01C038001C01C0708038038071003803807100380380E1003803 8062007007006400300300380021147C9325>I<1C0F802630C047406047806047007047 00708E00E00E00E00E00E00E00E01C01C01C01C01C01C01C038438038838038838070838 03107003303001C016147C931A>I<007C0001C3000301800E01C01E01C01C01E03C01E0 7801E07801E07801E0F003C0F003C0F003C0F00780F00700700F00700E00301800187000 07C00013147C9317>I<01C1E002621804741C04781C04701E04701E08E01E00E01E00E0 1E00E01E01C03C01C03C01C03C01C0380380780380700380E003C1C0072380071E000700 000700000E00000E00000E00000E00001C00001C0000FF8000171D809317>I<1C1E0026 61002783804787804707804703008E00000E00000E00000E00001C00001C00001C00001C 000038000038000038000038000070000030000011147C9313>114 D<00FC030206010C030C070C060C000F800FF007F803FC003E000E700EF00CF00CE00840 1020601F8010147D9313>I<018001C0038003800380038007000700FFF007000E000E00 0E000E001C001C001C001C003800380038003820704070407080708031001E000C1C7C9B 0F>I<0E00C01300E02301C04381C04701C04701C08703800E03800E03800E03801C0700 1C07001C07001C07101C0E20180E20180E201C1E400C264007C38014147C9318>I<0E03 801307802307C04383C04701C04700C08700800E00800E00800E00801C01001C01001C01 001C02001C02001C04001C04001C08000E300003C00012147C9315>I<0E00C1C01300E3 C02301C3E04381C1E04701C0E04701C060870380400E0380400E0380400E0380401C0700 801C0700801C0700801C0701001C0701001C0601001C0F02000C0F04000E13080003E1F0 001B147C931E>I<0383800CC4401068E01071E02071E02070C040E00000E00000E00000 E00001C00001C00001C00001C040638080F38080F38100E5810084C60078780013147D93 15>I<0E00C01300E02301C04381C04701C04701C08703800E03800E03800E03801C0700 1C07001C07001C07001C0E00180E00180E001C1E000C3C0007DC00001C00001C00003800 F03800F07000E06000C0C0004380003E0000131D7C9316>I<01C04003E08007F1800C1F 000802000004000008000010000020000040000080000100000200000401000802001002 003E0C0063FC0041F80080E00012147D9313>I E /Fh 4 56 df<187898181818181818 181818181818FF08107D8F0F>49 D<1F00618040C08060C0600060006000C00180030006 000C00102020207FC0FFC00B107F8F0F>I<1F00218060C060C000C0008001001F000080 00400060C060C060804060801F000B107F8F0F>I<40007FF07FE0804080400080010002 0002000600040004000C000C000C000C000C000C117F900F>55 D E /Fi 7 117 df<1E023F04618480480048002800300030003000200020002000200040 004000400F107F8A10>13 D<004000C00180018001800300030003000600060006000C00 0C000C00180018001800300030003000600060006000C000C0000A197D9210>61 D<0FE0FC01806001C04000C08000E100006600003C00003800003800007C0000CC00018E 00030600040700080300180380FC07E016117E9019>88 D<040C00000000003058989830 30606464683006127E910B>105 D<71F09A189C18981818183030303030323062606460 380F0B7E8A13>110 D<0F001080218020003E001F0001808080C00083007C00090B7D8A 0F>115 D<08181818FF30303030606062646438080F7E8E0C>I E /Fj 13 113 df0 D<70F8F8F87005057C8D0D>I<0001 000000030000000300000003000000030000000300000003000000030000000300000003 00000003000000030000000300000003000000030000FFFFFFFCFFFFFFFC000300000003 000000030000000300000003000000030000000300000003000000030000000300000003 00000003000000030000FFFFFFFCFFFFFFFC1E207E9E23>6 D<000000C0000003C00000 0F0000003C000000F0000003C00000070000001C00000078000001E00000078000001E00 000078000000E0000000780000001E0000000780000001E0000000780000001C00000007 00000003C0000000F00000003C0000000F00000003C0000000C000000000000000000000 0000000000000000000000000000000000007FFFFF80FFFFFFC01A247C9C23>20 DI<00000006000000000600000000060000000003000000000300000000 0380000000018000000000C0000000006000000000700000000018FFFFFFFFFFFFFFFFFF FF00000000180000000070000000006000000000C0000000018000000003800000000300 000000030000000006000000000600000000060028187E962D>33 D<003FF800FFF803C0000700000C0000180000300000300000600000600000C00000C000 00C00000FFFFF8FFFFF8C00000C00000C000006000006000003000003000001800000C00 0007000003C00000FFF8003FF8151C7C981E>50 D<40000080C0000180C0000180C00001 80C0000180C0000180C0000180C0000180C0000180C0000180C0000180C0000180C00001 80C0000180C0000180C0000180C0000180C0000180C0000180C0000180C0000180600003 0060000300300006001C001C000F00780003FFE00000FF8000191C7E9A1E>91 D<00FF800003FFE0000F0078001C001C00300006006000030060000300C0000180C00001 80C0000180C0000180C0000180C0000180C0000180C0000180C0000180C0000180C00001 80C0000180C0000180C0000180C0000180C0000180C0000180C0000180C0000180C00001 8040000080191C7E9A1E>I<000F0038006000E001C001C001C001C001C001C001C001C0 01C001C001C001C001C001C001C0038007001E00F8001E000700038001C001C001C001C0 01C001C001C001C001C001C001C001C001C001C001C000E000600038000F102D7DA117> 102 DI106 D<0000000008000000001800000000300000000030000000006000 0000006000000000C000000000C000000001800000000180000000030000000003000000 00060000000006000000000C000000000C00000000180000000018000000003000000000 300000000060000000006000000000C000060000C0001E000180002F000180004F000300 008780030000078006000003C006000003C00C000003C00C000001E018000001E0180000 00F030000000F030000000786000000078600000003CC00000003CC00000001F80000000 1F800000000F000000000F00000000060000000006000000252E7E8126>112 D E /Fk 5 113 df<00200040008001000300060006000C000C00180018003800300030 007000700070006000E000E000E000E000E000E000E000E000E000E000E000E000E00060 00700070007000300030003800180018000C000C0006000600030001000080004000200B 317A8113>0 D<800040002000100018000C000C00060006000300030003800180018001 C001C001C000C000E000E000E000E000E000E000E000E000E000E000E000E000E000C001 C001C001C001800180038003000300060006000C000C00180010002000400080000B317F 8113>I80 D88 D<000000000200000000060000 00000C000000000C00000000180000000018000000003000000000300000000060000000 006000000000C000000000C0000000018000000001800000000300000000030000000006 0000000006000000000C000000000C000000001800000000180000000030000000003000 000000600008000060001C0000C0003C0000C000CE000180000E000180000E0003000007 000300000700060000038006000003800C000001C00C000001C018000001E018000000E0 30000000E0300000007060000000706000000038C000000038C00000001D800000001D80 0000001F000000000F000000000E000000000600000027327C812A>112 D E /Fl 37 118 df<000F0000308000C0C00100400100600200C00400C0040080040180 083F00083E00080100080180100180100180100180100180300300300300300600280C00 44180043E000400000400000800000800000800000800000131D7F9614>12 D<01C007F0043808000C000C00040006000300030007800DC010C020C06060C060C060C0 60804080C0C080C18063003C000D187E9710>14 D<07C01C00300060006000FF00C000C0 00C000C000C000400020C01F000A0E7E8D0E>I<60F0F06004047D830A>58 D<60F0F070101020204040040A7D830A>I<0000300000F00003C0000700001C00007800 01E0000780000E0000380000F00000F000003800000E000007800001E000007800001C00 0007000003C00000F000003014167D921B>I<0008001800300030003000600060006000 C000C000C0018001800180030003000600060006000C000C000C00180018001800300030 003000600060006000C000C0000D217E9812>I<0000C00000C00001C00001C00003C000 05C00005E00008E00018E00010E00020E00020E00040E00080E00080E001FFF001007002 0070040070040070080070180070FE03FE17177F961A>65 D<07FFF800E00E00E00700E0 0300E00301C00301C00701C00701C00E03803C03FFF003FFF003803C07001C07000E0700 0E07000E0E001C0E001C0E00380E00701C01E0FFFF0018177F961B>I<001F8200E04403 802C07001C0C001C1C0008380008300008700008600000E00000E00000E00000C00000C0 0020C00020C00040E000406000806001003002001C1C0007E00017177E9619>I<07FFF8 0000E00E0000E0030000E0038000E0018001C001C001C001C001C000C001C000C0038001 C0038001C0038001C0038001C0070003800700038007000300070007000E000E000E000C 000E0018000E0070001C01C000FFFF00001A177F961D>I<07FFFF8000E0038000E00100 00E0010000E0010001C0010001C0010001C0400001C04000038080000381800003FF8000 03818000070100000701020007010200070004000E0004000E000C000E0008000E001800 1C007000FFFFF00019177F961A>I<07FF0000E00000E00000E00000E00001C00001C000 01C00001C0000380000380000380000380000700000700080700080700100E00100E0030 0E00200E00601C01E0FFFFC015177F9618>76 D<07F0000FE000F0001E0000B8001E0000 B8002E0000B8004E000138005C000138009C000138011C00011C011C00021C023800021C 043800021C043800021C083800041C107000040E107000040E207000040E407000080E40 E000080E80E000080F00E000080700E000180601C000FE040FF80023177F9622>I<07F0 07F800F000C000B8008000B80080009C0080011C0100011E0100010E0100010E01000207 02000207020002038200020382000401C4000401C4000400E4000400E400080078000800 7800080038000800380018001000FE0010001D177F961C>I<001FC000707001C0180300 1C06000C0E000E1C000E18000E38000E30000E70000E70000E70000E70001CE0001C6000 387000387000707000E03801C01803800E0E0003F00017177F961B>I<07FFF800E00E00 E00700E00700E00701C00701C00701C00701C00E03801C03807003FFC003800007000007 00000700000700000E00000E00000E00000E00001C0000FF800018177F9616>I<07FFF0 0000E01C0000E0060000E0070000E0070001C0070001C0070001C0070001C00E0003801C 000380700003FF80000380E000070070000700380007003800070038000E0070000E0070 000E0070800E0070801C003100FF801E0019177F961B>82 D<003E1000C1A00100E00200 600600600C00400C00400E00000F000007E00007FC0001FE00003F000007800003800003 80200180400300400300600600600400D8180087E00014177E9615>I<1FFFFE381C0E20 1C04601C04401C0440380480380400380000380000700000700000700000700000E00000 E00000E00000E00001C00001C00001C00001C00003C0003FFC0017177F9615>I<03FE0F E0007807000078060000380C0000380800003C1000001C2000001E4000000E8000000F00 000007000000070000000F8000001380000023C0000061C00000C1C0000181E0000100E0 000200F000040070001C007000FF03FE001B177F961D>88 D<071018F0307060706060C0 60C060C06080C080C480C4C1C446C838700E0E7E8D13>97 D<07C00C20107020706000C0 00C000C00080008000C010C02060C03F000C0E7E8D0F>99 D<003E000C000C000C000C00 18001800180018073018F0307060706060C060C060C06080C080C480C4C1C446C838700F 177E9612>I<07C01C20301060106020FFC0C000C000C000C000C010402060C01F000C0E 7E8D10>I<0300038003000000000000000000000000001C002400460046008C000C0018 001800180031003100320032001C0009177F960C>105 D<001800380010000000000000 00000000000001C0022004300430086000600060006000C000C000C000C0018001800180 01806300E300C60078000D1D80960E>I<1F0006000600060006000C000C000C000C0018 1C1866188E190C32003C003F00318060C060C460C460C4C0C8C0700F177E9612>I<3E0C 0C0C0C181818183030303060606060C0C8C8C8D07007177E960B>I<383C1E0044C66300 47028100460301008E0703000C0603000C0603000C060300180C0600180C0620180C0C20 180C0C40301804C0301807001B0E7F8D1F>I<383C0044C6004702004602008E06000C06 000C06000C0600180C00180C40181840181880300980300E00120E7F8D15>I<1C3C2246 2382230346030603060306030C060C060C0C0C081A3019E018001800300030003000FC00 1014808D12>112 D<071018D0307060706060C060C060C06080C080C080C0C1C0478039 80018001800300030003001FC00C147E8D10>I<30F049184E384C309C00180018001800 3000300030003000600060000D0E7F8D10>I<07C00C201870187038001E000FC003E000 606060E060C0C0C1803F000C0E7E8D10>I<030003000600060006000600FFC00C000C00 0C001800180018001800300030803080310032001C000A147F930D>I<1C020026060046 0600460600860C000C0C000C0C000C0C001818001818801818801838800C5900078E0011 0E7F8D14>I E /Fm 17 127 df<001800001800003C00003C00004E00004E0000870000 87000103800303C00201C00601E00400E00800F008007010007810003820003C20001C40 001E7FFFFEFFFFFFFFFFFF18177E961D>1 D<0102040C1818303070606060E0E0E0E0E0 E0E0E0E0E060606070303018180C04020108227D980E>40 D<8040203018180C0C0E0606 06070707070707070707070606060E0C0C18183020408008227E980E>I<003000003000 003000003000003000003000003000003000003000003000003000FFFFFCFFFFFC003000 00300000300000300000300000300000300000300000300000300000300016187E931B> 43 D<06000E00FE000E000E000E000E000E000E000E000E000E000E000E000E000E000E 000E000E000E00FFE00B157D9412>49 D<0F8030E040708030C038E03840380038007000 70006000C00180030006000C08080810183FF07FF0FFF00D157E9412>I<0FE030306018 701C701C001C00180038006007E000300018000C000E000EE00EE00EC00C401830300FE0 0F157F9412>I<00300030007000F001F001700270047008701870107020704070C070FF FE0070007000700070007003FE0F157F9412>I<60307FE07FC044004000400040004000 4F8070E040700030003800384038E038E0388030406020C01F000D157E9412>I<40007F FE7FFC7FF8C008801080200040008000800100030003000200060006000E000E000E000E 000E0004000F167E9512>55 D61 D91 D93 D<0F9E18E330607070707070 70306018C02F80200060003FE03FF83FFC600EC006C006C006600C38380FE010157F8D12 >103 D108 D<07C018303018600C600CE00EE00EE00EE00EE00E701C3018183007C00F0E7F8D12> 111 D<3C207FC087800B037D9512>126 D E /Fn 48 122 df<00800100020004000C00 080018003000300030006000600060006000E000E000E000E000E000E000E000E000E000 E0006000600060006000300030003000180008000C00040002000100008009267D9B0F> 40 D<8000400020001000180008000C0006000600060003000300030003000380038003 80038003800380038003800380038003000300030003000600060006000C000800180010 0020004000800009267E9B0F>I<000C0000000C0000000C0000000C0000000C0000000C 0000000C0000000C0000000C0000000C0000000C0000000C0000FFFFFF80FFFFFF80000C 0000000C0000000C0000000C0000000C0000000C0000000C0000000C0000000C0000000C 0000000C0000000C0000191A7E951E>43 D45 D<60F0F06004047D830B>I<07E01C38381C300C700E60066006E007E007E007E007E007 E007E007E007E007E00760066006700E300C381C1C3807E010187F9713>48 D<03000700FF000700070007000700070007000700070007000700070007000700070007 00070007000700070007007FF80D187D9713>I<001800180038007800F800B801380238 0238043808381838103820384038C038FFFF00380038003800380038003803FF10187F97 13>52 D<40007FFF7FFE7FFE400480088010801000200040004000800180010003000300 0700060006000E000E000E000E000E00040010197E9813>55 D<07E01818300C20066006 60067006780C3E181F3007C003E00CF8307C601E600FC007C003C003C003600220041818 07E010187F9713>I<07E01C303018700C600EE006E006E007E007E0076007700F301718 2707C700070006000E000C700C7018603030600F8010187F9713>I<60F0F06000000000 0000000060F0F0701010102020404004177D8F0B>59 D<000C0000000C0000000C000000 1E0000001E0000002F000000270000002700000043800000438000004380000081C00000 81C0000181E0000100E0000100E00003FFF0000200700002007000040038000400380004 00380008001C0008001C003C001E00FF00FFC01A1A7F991D>65 D<003F0201C0C603002E 0E001E1C000E1C0006380006780002700002700002F00000F00000F00000F00000F00000 F000007000027000027800023800041C00041C00080E000803003001C0C0003F00171A7E 991C>67 D70 D<003F020001C0C60003002E000E001E001C 000E001C00060038000600780002007000020070000200F0000000F0000000F0000000F0 000000F0000000F001FFC070000E0070000E0078000E0038000E001C000E001C000E000E 000E000300160001C06600003F82001A1A7E991E>I73 D77 DI<0FC21836200E6006C006C002C002C002E00070 007E003FE01FF803FC007E000E00070003800380038003C002C006E004D81887E0101A7E 9915>83 D<7FFFFF00701C0700401C0100401C0100C01C0180801C0080801C0080801C00 80001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C00 00001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C000003FFE0 00191A7F991C>II88 D91 D93 D<1FC000387000383800101C00001C00001C0003FC001E1C00381C00701C00E01C00E01C 80E01C80E03C80705F801F8F0011107F8F13>97 DI<07F8 1C1C381C70087000E000E000E000E000E000E0007000700438081C1807E00E107F8F11> I<003F0000070000070000070000070000070000070000070000070000070003E7000C17 00180F00300700700700E00700E00700E00700E00700E00700E00700600700700700380F 001C370007C7E0131A7F9915>I<07C01C3030187018600CE00CFFFCE000E000E000E000 6000700438081C1807E00E107F8F11>I<01F007180E381C101C001C001C001C001C001C 00FFC01C001C001C001C001C001C001C001C001C001C001C001C001C001C00FF800D1A80 990C>I<0FCF001871803030007038007038007038007038003030001860002FC0006000 006000007000003FF0003FFC001FFE00600F00C00300C00300C00300C00300600600381C 0007E00011187F8F13>II<183C3C18000000000000FC1C 1C1C1C1C1C1C1C1C1C1C1C1C1CFF081A80990A>I108 DII<07E01C38300C700E 6006E007E007E007E007E007E0076006700E381C1C3807E010107F8F13>II<03 E1000C1300180B00300F00700700E00700E00700E00700E00700E00700E0070070070070 0700380F001C370007C700000700000700000700000700000700000700003FE013177F8F 14>II<1F2060E04020C020C020F0007F003FC01FE000F080708030C030C020F040 8F800C107F8F0F>I<0800080008000800180018003800FFC03800380038003800380038 0038003800382038203820382018201C4007800B177F960F>IIIIII E /Fo 4 107 df0 D<0C000C00CCC0EDC07F800C007F80EDC0CCC00C000C000A0B7D8B10>3 D<081C1C3838383070706060C0C0060D7E8D09>48 D106 D E /Fp 47 121 df<007E000001C30000 030180800E00C0801E00E0801C00E1003C00E1007800E1007800E2007800E400F000E400 F000E800F000F000F000F000F000E0007000E00070016000300671001818320007E01C00 19147E931D>11 D<0000F800030600040600080300100300200300400700400700800700 800601000E01000C0107F80104700207D802001C02001C02001E04001E04001E04001E04 001E08003C08003C08003C0800781800701400F01400E01201C0218700207C0020000020 000040000040000040000040000080000080000080000018297F9F1A>I<03C0020FE004 1FF0043FF808701808400C10C00410800420000220000240000240000280000280000300 000300000300000200000200000200000600000600000600000C00000C00000C00000C00 001800001800001800001000171E7F9318>I<003E00007FC00083C00101800100000180 0001800001C00000C00000E00000E00000700000780000780001BC00071E000E1E001C0E 00180E00380F00700F00700700700700E00600E00E00E00E00E00C00E00C006018006018 003030001860000F800012217EA014>I<007C018007000E001C003C003800780078007F F0F000F000F000700070007000300038000C1807E00E147E9312>I<70F8F8F87005057C 840D>58 D<70F0F8F878080808101010202040050E7C840D>I<000001C0000007800000 1E00000078000001E00000078000000E00000038000000F0000003C000000F0000003C00 0000F0000000F00000003C0000000F00000003C0000000F0000000380000000E00000007 80000001E0000000780000001E0000000780000001C01A1A7C9723>I<0000400000C000 0180000180000180000300000300000300000600000600000C00000C00000C0000180000 180000180000300000300000600000600000600000C00000C00000C00001800001800001 80000300000300000600000600000600000C00000C00000C000018000018000030000030 0000300000600000600000600000C00000C00000122D7EA117>II<000002000000 060000000E0000000E0000001E0000001F0000002F0000006F0000004F0000008F000000 8F0000010F0000030F0000020F0000040F8000040F800008078000180780001007800020 078000200780007FFF800080078000800780010007C0010003C0020003C0040003C00400 03C00C0003C03C0007C0FF003FFC1E207E9F22>65 D<01FFFFE0001E0078001E003C001E 001C001E001E003C001E003C001E003C001E003C001E0078003C0078003C007800780078 00F000F003C000FFFF0000F007C000F000E001E000F001E0007801E0007801E0007803C0 007803C0007803C0007803C00070078000F0078001E0078003C0078007800F001E00FFFF F0001F1F7E9E22>I<00007F00800003C0C180000E00230000380017000070000F0000E0 000F0001C0000600038000060007000006000F000006000E000004001E000004003C0000 00003C000000007800000000780000000078000000007800000000F000000000F0000000 00F000000000F00000000070000020007000002000700000200070000040003800008000 38000080001C000100000E00060000070018000001C0600000007F80000021217F9F21> I<01FFFFE000001E003800001E000E00001E000700001E000700003C000380003C000380 003C0001C0003C0001C000780001C000780001C000780001C000780001C000F00003C000 F00003C000F00003C000F00003C001E000078001E000078001E000070001E0000F0003C0 000E0003C0001E0003C0001C0003C00038000780007000078000E000078001C000078007 00000F001C0000FFFFF00000221F7E9E26>I<01FFFFFF80001E000F00001E000300001E 000300001E000100003C000100003C000100003C000100003C0001000078020200007802 00000078020000007806000000F00C000000FFFC000000F00C000000F00C000001E00800 0001E008000001E008000001E000040003C000080003C000080003C000100003C0001000 078000200007800060000780004000078001C0000F0007C000FFFFFF8000211F7E9E22> I<01FFFFFF001E001E001E0006001E0006001E0002003C0002003C0002003C0002003C00 020078000400780200007802000078020000F0040000F00C0000FFFC0000F00C0001E008 0001E0080001E0080001E0080003C0000003C0000003C0000003C0000007800000078000 0007800000078000000F800000FFFC0000201F7E9E1D>I<01FFF0001F00001E00001E00 001E00003C00003C00003C00003C0000780000780000780000780000F00000F00000F000 00F00001E00001E00001E00001E00003C00003C00003C00003C000078000078000078000 0780000F8000FFF000141F7E9E14>73 D<01FFF800001F0000001E0000001E0000001E00 00003C0000003C0000003C0000003C00000078000000780000007800000078000000F000 0000F0000000F0000000F0000001E0000001E0000001E0000001E0004003C0008003C000 8003C0018003C0010007800300078003000780060007800E000F007C00FFFFFC001A1F7E 9E1F>76 D<01FE00000FF8001E00001F80001700001F00001700002F00001700004F0000 2700005E00002700009E00002700011E00002700011E00004380023C00004380023C0000 4380043C00004380083C000083800878000083801078000083802078000081C020780001 01C040F0000101C080F0000101C080F0000101C100F0000201C101E0000201C201E00002 01C401E0000200E401E0000400E803C0000400F003C0000400F003C0000C00E003C0001E 00C007C000FFC0C07FFC002D1F7E9E2C>I<01FF001FF8001F0003C0001F800100001780 010000178001000023C002000023C002000021E002000021E002000041F004000040F004 000040F004000040780400008078080000807C080000803C080000803C080001001E1000 01001E100001000F100001000F100002000FA000020007A000020007A000020003E00004 0003C000040003C000040001C0000C0001C0001E00008000FFC0008000251F7E9E25>I< 0000FF00000781C0001C00E0003800700070003801C0001C03C0001C0380001E0700000E 0F00000E1E00000E1E00000E3C00000E3C00000E7800001E7800001E7800001E7800001E F000003CF000003CF0000038F0000078F0000070700000F0700001E0780001C078000380 380007001C000E001C001C000F0070000381C00000FF00001F217F9F23>I<01FFFFE000 1E0078001E001C001E000E001E000F003C000F003C000F003C000F003C000F0078001E00 78001E0078003C0078007800F000E000F003C000FFFE0000F0000001E0000001E0000001 E0000001E0000003C0000003C0000003C0000003C0000007800000078000000780000007 8000000F800000FFF80000201F7E9E1D>I<01FFFF80001E00F0001E0038001E001C001E 001C003C001E003C001E003C001E003C001E0078003C0078003C00780078007800F000F0 01C000F0070000FFF80000F00E0001E0070001E0078001E0038001E003C003C0078003C0 078003C0078003C0078007800F0007800F0207800F0207800F040F800704FFF803080000 01F01F207E9E23>82 D<0003F040000C08C0003005800060038000C0038001C001800180 01000380010003800100038001000380000003C0000003E0000003FC000001FFC00000FF F000007FF800001FF8000001FC0000007C0000003C0000001C0000001C0020001C002000 1C00200018006000380060003000600070007000E000E8018000C603000081FC00001A21 7E9F1C>I<0FFFFFFC1E03C0381803C0181003C0082003C0082007800860078008400780 0840078008800F0010000F0000000F0000000F0000001E0000001E0000001E0000001E00 00003C0000003C0000003C0000003C00000078000000780000007800000078000000F000 0000F0000000F0000000F0000001F000007FFFC0001E1F7F9E1B>I<00FFF01FF8000FC0 0780000F80060000078004000007C008000007C010000003C020000003E040000001E0C0 000001F180000001F300000000F200000000FC0000000078000000007C000000007C0000 00007C00000000BE000000011E000000021F000000041F0000000C0F000000180F800000 10078000002007C000004007C000008003C000010003E000070001E0001F0003F000FFC0 1FFE00251F7F9E26>88 D<00F1800389C00707800E03801C03803C038038070078070078 0700780700F00E00F00E00F00E00F00E10F01C20F01C20703C20705C40308C400F078014 147E9318>97 D<07803F8007000700070007000E000E000E000E001C001C001CF01D0C3A 0E3C0E380F380F700F700F700F700FE01EE01EE01EE01CE03CE038607060E031C01F0010 207E9F14>I<007C0001C3000700800E07801E07801C07003C0200780000780000780000 F00000F00000F00000F00000F000007001007002003004001838000FC00011147E9314> I<0000780003F80000700000700000700000700000E00000E00000E00000E00001C00001 C000F1C00389C00707800E03801C03803C0380380700780700780700780700F00E00F00E 00F00E00F00E10F01C20F01C20703C20705C40308C400F078015207E9F18>I<007C0182 07010E011C013C013802780C7BF07C00F000F000F000F000700070017002300418380FC0 10147E9315>I<00E001E001E000C000000000000000000000000000000E001300238043 80438043808700070007000E000E001C001C001C20384038403840388019000E000B1F7E 9E10>105 D<0000C00001E00001E00001C0000000000000000000000000000000000000 000000001E00002300004380008380010380010380020700000700000700000700000E00 000E00000E00000E00001C00001C00001C00001C00003800003800003800003800007000 00700030700078E000F1C0006380003E00001328819E13>I<01E0000FE00001C00001C0 0001C00001C0000380000380000380000380000700000700000701E00706100E08700E10 F00E20F00E20601C40001D80001E00001FC000387000383800383800381C207038407038 40703840701880E01880600F0014207E9F18>I<01C01FC0038003800380038007000700 070007000E000E000E000E001C001C001C001C0038003800380038007000700070007100 E200E200E200E200640038000A207E9F0E>I<1E07C07C00231861860023A032030043C0 3403004380380380438038038087007007000700700700070070070007007007000E00E0 0E000E00E00E000E00E00E000E00E01C101C01C01C201C01C038201C01C038401C01C018 4038038018801801800F0024147E9328>I<1E07802318C023A06043C070438070438070 8700E00700E00700E00700E00E01C00E01C00E01C00E03821C03841C07041C07081C0308 3803101801E017147E931B>I<007C0001C3000301800E01C01E01C01C01E03C01E07801 E07801E07801E0F003C0F003C0F003C0F00780F00700700F00700E0030180018700007C0 0013147E9316>I<03C1E004621804741C08781C08701E08701E10E01E00E01E00E01E00 E01E01C03C01C03C01C03C01C0380380780380700380E003C1C0072380071E0007000007 00000E00000E00000E00000E00001C00001C0000FFC000171D819317>I<00F0400388C0 0705800E03801C03803C0380380700780700780700780700F00E00F00E00F00E00F00E00 F01C00F01C00703C00705C0030B8000F3800003800003800007000007000007000007000 00E00000E0000FFC00121D7E9314>I<1C1E002621004743804787804707804703008E00 000E00000E00000E00001C00001C00001C00001C00003800003800003800003800007000 0030000011147E9315>I<00FC000303000600800C01800C03800C03000E00000F80000F F80007FC0001FE00001F00000700700700F00600F00600E004004008002030001FC00011 147E9315>I<018001C0038003800380038007000700FFF807000E000E000E000E001C00 1C001C001C003800380038003810702070207040708031001E000D1C7F9B10>I<0F0060 1180702180E021C0E041C0E04380E08381C00701C00701C00701C00E03800E03800E0380 0E03840E07080C07080C07080E0F1006131003E1E016147E931A>I<1E01C02303C02303 E04381E04300E04700608700400E00400E00400E00401C00801C00801C00801C01001C01 001C02001C04000C04000E180003E00013147E9316>I<0F006070118070F02180E0F821 C0E07841C0E0384380E0188381C0100701C0100701C0100701C0100E0380200E0380200E 0380200E0380400E0380400E0380800E078080060781000709C20001F07C001D147E9321 >I<03C1C00C62201034701038F02038F020386040700000700000700000700000E00000 E00000E00000E02061C040F1C040F1C080E2C080446300383C0014147E931A>I E /Fq 83 127 df<00008000000001C000000001C000000003E000000003E000000005F0 00000004F000000008F80000000878000000107C000000103C000000203E000000201E00 0000401F000000400F000000800F80000080078000010007C000010003C000020003E000 020001E000040001F000040000F000080000F80008000078001000007C001000003C0020 00003E002000001E007FFFFFFF007FFFFFFF00FFFFFFFF8021207E9F26>1 D<001FE0000070380001C00E0003800700070003800F0003C01E0001E03E0001F03C0000 F07C0000F87C0000F878000078F800007CF880047CF880047CF8FFFC7CF8FFFC7CF8FFFC 7CF880047CF880047CF800007C780000787C0000F87C0000F83C0000F03E0001F01E0001 E00F0003C0070003800380070001C00E0000703800001FE0001E217E9F23>I<003FC000 01E0780007801E000F000F001E0007803C0003C07C0003E07C0003E0F80001F0F80001F0 F80001F0F80001F0F80001F0F80001F0780001E07C0003E07C0003E03C0003C03C0003C0 1E0007800E00070007000E0007000E0003000C0001801800818018108080101080C03010 404020207FC03FE07FC03FE07FC03FE01C207E9F21>10 D<001F83E000F06E3001C07878 0380F8780300F03007007000070070000700700007007000070070000700700007007000 FFFFFF800700700007007000070070000700700007007000070070000700700007007000 070070000700700007007000070070000700700007007000070070000700700007007000 070070003FE3FF001D20809F1B>I<003F0000E0C001C0C00381E00701E00701E0070000 070000070000070000070000070000FFFFE00700E00700E00700E00700E00700E00700E0 0700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E0 3FC3FC1620809F19>I<001F81F80000F04F040001C07C06000380F80F000300F00F0007 00F00F00070070000007007000000700700000070070000007007000000700700000FFFF FFFF00070070070007007007000700700700070070070007007007000700700700070070 070007007007000700700700070070070007007007000700700700070070070007007007 0007007007000700700700070070070007007007003FE3FE3FE02320809F26>14 D<70F8F8F8F8F8F8F8707070707070707070702020202020000000000070F8F8F8700521 7CA00D>33 D<7038F87CFC7EFC7E743A0402040204020804080410081008201040200F0E 7F9F17>I<70F8FCFC74040404080810102040060E7C9F0D>39 D<004000800100030006 0004000C001800180038003000300070006000600060006000E000E000E000E000E000E0 00E000E000E000E000E000E00060006000600060007000300030003800180018000C0004 00060003000100008000400A2E7BA112>I<8000400020003000180008000C0006000600 0700030003000380018001800180018001C001C001C001C001C001C001C001C001C001C0 01C001C001800180018001800380030003000700060006000C0008001800300020004000 80000A2E7EA112>I<000300000003000000030000000300000003000000030000000300 000003000000030000000300000003000000030000000300000003000000030000FFFFFF FCFFFFFFFC00030000000300000003000000030000000300000003000000030000000300 00000300000003000000030000000300000003000000030000000300001E207E9A23>43 D<70F0F8F878080808101010202040050E7C840D>II<70F8F8F8 7005057C840D>I<0000400000C000018000018000018000030000030000030000060000 0600000C00000C00000C0000180000180000180000300000300000600000600000600000 C00000C00000C0000180000180000180000300000300000600000600000600000C00000C 00000C0000180000180000300000300000300000600000600000600000C00000C0000012 2D7EA117>I<03F0000E1C001C0E00180600380700700380700380700380700380F003C0 F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0 7003807003807003807807803807001806001C0E000E1C0003F000121F7E9D17>I<0080 03800F80F380038003800380038003800380038003800380038003800380038003800380 03800380038003800380038003800380038007C0FFFE0F1E7C9D17>I<03F0000C1C0010 0E00200700400780800780F007C0F803C0F803C0F803C02007C00007C000078000078000 0F00000E00001C0000380000700000600000C0000180000300000600400C004018004010 00803FFF807FFF80FFFF80121E7E9D17>I<03F0000C1C00100E00200F00780F80780780 780780380F80000F80000F00000F00001E00001C0000700007F000003C00000E00000F00 0007800007800007C02007C0F807C0F807C0F807C0F00780400780400F00200E00183C00 07F000121F7E9D17>I<000600000600000E00000E00001E00002E00002E00004E00008E 00008E00010E00020E00020E00040E00080E00080E00100E00200E00200E00400E00C00E 00FFFFF0000E00000E00000E00000E00000E00000E00000E0000FFE0141E7F9D17>I<18 03001FFE001FFC001FF8001FE00010000010000010000010000010000010000011F00016 1C00180E001007001007800003800003800003C00003C00003C07003C0F003C0F003C0E0 0380400380400700200600100C0008380007E000121F7E9D17>I<007C00018200070100 0E03800C0780180780380300380000780000700000700000F1F000F21C00F40600F80700 F80380F80380F003C0F003C0F003C0F003C0F003C07003C07003C0700380380380380700 1807000C0E00061C0001F000121F7E9D17>I<4000007FFFE07FFFC07FFFC04000808001 0080010080020000040000040000080000100000100000200000200000600000600000E0 0000C00001C00001C00001C00001C00003C00003C00003C00003C00003C00003C00003C0 00018000131F7E9D17>I<03F0000C0C0010060030030020018060018060018060018070 01807803003E03003F06001FC8000FF00003F80007FC000C7E00103F00300F8060078060 01C0C001C0C000C0C000C0C000C0C000806001802001001002000C0C0003F000121F7E9D 17>I<03F0000E18001C0C00380600380700700700700380F00380F00380F003C0F003C0 F003C0F003C0F003C07007C07007C03807C0180BC00E13C003E3C0000380000380000380 000700300700780600780E00700C002018001070000FC000121F7E9D17>I<70F8F8F870 0000000000000000000070F8F8F87005147C930D>I<70F8F8F870000000000000000000 0070F0F8F878080808101010202040051D7C930D>I<7FFFFFF8FFFFFFFC000000000000 0000000000000000000000000000000000000000000000000000FFFFFFFC7FFFFFF81E0C 7E9023>61 D<000100000003800000038000000380000007C0000007C0000007C0000009 E0000009E0000009E0000010F0000010F0000010F0000020780000207800002078000040 3C0000403C0000C03E0000801E0000801E0001FFFF0001000F0001000F00020007800200 078002000780040003C0040003C00C0003C01E0003E0FF801FFE1F207F9F22>65 DI<000FE01000381C3000E00270 03C00170078000F00F0000701E0000701E0000303C0000303C0000107C00001078000010 F8000000F8000000F8000000F8000000F8000000F8000000F8000000F8000000F8000000 780000007C0000103C0000103C0000101E0000201E0000200F0000200780004003C00080 00E0030000380C00000FF0001C217E9F21>IIII<000FE01000381C3000E0027003C00170078000F0 0F0000701E0000701E0000303C0000303C0000107C00001078000010F8000000F8000000 F8000000F8000000F8000000F8000000F8000000F8003FFEF80001F0780000F07C0000F0 3C0000F03C0000F01E0000F01E0000F00F0000F0078000F003C0017000E0023000380C10 000FF0001F217E9F24>III<07FFC0003E 00001E00001E00001E00001E00001E00001E00001E00001E00001E00001E00001E00001E 00001E00001E00001E00001E00001E00001E00001E00001E00001E00201E00F81E00F81E 00F81E00F01C00403C006038001070000FC00012207F9E17>IIIII<001FE0000070380001C00E0003800700070003800F0003C01E00 01E03C0000F03C0000F07C0000F87C0000F878000078F800007CF800007CF800007CF800 007CF800007CF800007CF800007CF800007CF800007C780000787C0000F87C0000F83C00 00F03E0001F01E0001E00F0003C0070003800380070001E01E0000703800001FE0001E21 7E9F23>II82 D<03F0400C0CC01803C03001C06000C060 00C0E000C0E00040E00040E00040F00000F800007C00007F80003FF8001FFF0007FF8000 FFC0001FE00003E00001E00000F0000070800070800070800070800070C00060C000E0E0 00C0F80180C6030081FC0014217E9F19>I<7FFFFFE0780F01E0600F0060400F0020400F 0020C00F0030800F0010800F0010800F0010800F0010000F0000000F0000000F0000000F 0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F 0000000F0000000F0000000F0000000F0000000F0000000F0000001F800003FFFC001C1F 7E9E21>IIII<7FF81FF80FE007C007C0030003C0020003E0060001F0040000F0080000F8 180000781000003C2000003E6000001E4000000F8000000F8000000780000003C0000007 E0000005E0000008F0000018F8000010780000207C0000603E0000401E0000801F000100 0F8001000780020007C0060003C01F0007E0FFC01FFE1F1F7F9E22>II91 D<080410082010201040204020804080408040B85CFC7EFC7E7C3E381C0F0E7A9F17>I< FFFF03030303030303030303030303030303030303030303030303030303030303030303 03030303030303FFFF082D80A10D>I<1FE000303000781800781C00300E00000E00000E 00000E0000FE00078E001E0E00380E00780E00F00E10F00E10F00E10F01E10781E103867 200F83C014147E9317>97 D<1C0000FC00001C00001C00001C00001C00001C00001C0000 1C00001C00001C00001C00001C7C001D87001E01801E00C01C00E01C00701C00701C0078 1C00781C00781C00781C00781C00781C00701C00F01C00E01E00C01A0180198700107C00 15207E9F19>I<01FC000706001C0F00380F00380600780000700000F00000F00000F000 00F00000F00000F000007000007800003800803800801C010007060001F80011147F9314 >I<0001C0000FC00001C00001C00001C00001C00001C00001C00001C00001C00001C000 01C001F1C0070DC00C03C01801C03801C07801C07001C0F001C0F001C0F001C0F001C0F0 01C0F001C07001C07001C03801C01803C00C03C0070DC001F1F815207F9F19>I<03F000 0E1C001C0E00380700380700700700700380F00380F00380FFFF80F00000F00000F00000 7000007000003800803800801C010007060001F80011147F9314>I<007C01C6030F070F 0E060E000E000E000E000E000E000E00FFF00E000E000E000E000E000E000E000E000E00 0E000E000E000E000E000E000E000E000E007FE01020809F0E>I<0000E003E3300E3C30 1C1C30380E00780F00780F00780F00780F00780F00380E001C1C001E380033E000200000 2000003000003000003FFE001FFF801FFFC03001E0600070C00030C00030C00030C00030 6000603000C01C038003FC00141F7F9417>I<1C0000FC00001C00001C00001C00001C00 001C00001C00001C00001C00001C00001C00001C7C001C86001D03001E03801E03801C03 801C03801C03801C03801C03801C03801C03801C03801C03801C03801C03801C03801C03 801C0380FF8FF014207E9F19>I<38007C007C007C003800000000000000000000000000 1C00FC001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C00 1C00FF80091F7F9E0C>I<00E001F001F001F000E0000000000000000000000000007007 F000F0007000700070007000700070007000700070007000700070007000700070007000 7000700070007000706070F060F0C061803F000C28829E0E>I<1C0000FC00001C00001C 00001C00001C00001C00001C00001C00001C00001C00001C00001C1FE01C07801C06001C 04001C08001C10001C20001C60001CE0001DF0001E70001C38001C3C001C1C001C0E001C 0F001C07001C07801C07C0FF9FF014207E9F18>I<1C00FC001C001C001C001C001C001C 001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C 001C001C001C001C001C00FF8009207F9F0C>I<1C3E03E000FCC30C30001D039038001E 01E01C001E01E01C001C01C01C001C01C01C001C01C01C001C01C01C001C01C01C001C01 C01C001C01C01C001C01C01C001C01C01C001C01C01C001C01C01C001C01C01C001C01C0 1C001C01C01C00FF8FF8FF8021147E9326>I<1C7C00FC86001D03001E03801E03801C03 801C03801C03801C03801C03801C03801C03801C03801C03801C03801C03801C03801C03 801C0380FF8FF014147E9319>I<01F800070E001C03803801C03801C07000E07000E0F0 00F0F000F0F000F0F000F0F000F0F000F07000E07000E03801C03801C01C0380070E0001 F80014147F9317>I<1C7C00FD87001E01801E01C01C00E01C00F01C00701C00781C0078 1C00781C00781C00781C00781C00701C00F01C00E01E01C01E03801D87001C7C001C0000 1C00001C00001C00001C00001C00001C00001C0000FF8000151D7E9319>I<01F040070C C00E02C01C03C03801C07801C07001C0F001C0F001C0F001C0F001C0F001C0F001C07001 C07801C03801C01C03C00C05C00709C001F1C00001C00001C00001C00001C00001C00001 C00001C00001C0000FF8151D7F9318>I<1CF0FD181E3C1E3C1E181C001C001C001C001C 001C001C001C001C001C001C001C001C001C00FFC00E147E9312>I<0FC830386018C008 C008C008E0007C003FE01FF007F8003C800E8006C006C006C004E00CD81887E00F147F93 12>I<020002000200060006000E000E003E00FFF80E000E000E000E000E000E000E000E 000E000E000E000E040E040E040E040E040708030801F00E1C7F9B12>I<1C0380FC1F80 1C03801C03801C03801C03801C03801C03801C03801C03801C03801C03801C03801C0380 1C03801C03801C07800C0780061B8003E3F014147E9319>IIIII<7FFF700E600E401C40384078407000E001E001C0 0380078007010E011E011C0338027006700EFFFE10147F9314>I<1C043F0843F080E00E 047C9D17>126 D E /Fr 40 121 df45 D<000E00001E00007E0007FE00FFFE00FFFE00F8FE0000FE0000FE0000FE00 00FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE00 00FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE00 00FE0000FE00FFFFFEFFFFFEFFFFFE17277BA622>49 D<00FF800007FFF0000FFFFC001E 03FE003800FF807C003F80FE003FC0FF001FC0FF001FE0FF000FE0FF000FE07E000FE03C 001FE000001FE000001FC000001FC000003F8000003F0000007E000000FC000000F80000 01F0000003E00000078000000F0000001E0000003C00E0007000E000E000E001C001C003 8001C0060001C00FFFFFC01FFFFFC03FFFFFC07FFFFFC0FFFFFF80FFFFFF80FFFFFF801B 277DA622>I<007F800003FFF00007FFFC000F81FE001F007F003F807F003F803F803F80 3F803F803F801F803F801F003F8000007F0000007F0000007E000000FC000001F8000007 F00000FFC00000FFC0000001F80000007E0000003F0000003F8000001FC000001FC00000 1FE000001FE03C001FE07E001FE0FF001FE0FF001FE0FF001FC0FF003FC0FE003F807C00 7F003F01FE001FFFFC0007FFF00000FF80001B277DA622>I<00000F0000000F0000001F 0000003F0000007F000000FF000001FF000001FF000003BF0000073F00000E3F00001C3F 00003C3F0000383F0000703F0000E03F0001C03F0003803F0007803F0007003F000E003F 001C003F0038003F0070003F00F0003F00FFFFFFF8FFFFFFF8FFFFFFF800007F0000007F 0000007F0000007F0000007F0000007F0000007F0000007F00001FFFF8001FFFF8001FFF F81D277EA622>I<180003001F801F001FFFFE001FFFFC001FFFF8001FFFF0001FFFC000 1FFF00001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C7FC000 1DFFF8001F80FC001E003F0008003F0000001F8000001FC000001FC000001FE000001FE0 18001FE07C001FE0FE001FE0FE001FE0FE001FE0FE001FC0FC001FC078003F8078003F80 3C007F001F01FE000FFFFC0003FFF00000FF80001B277DA622>I<0007F800003FFE0000 FFFF0001FC078003F00FC007C01FC00F801FC01F801FC01F001FC03F000F803F0000007E 0000007E0000007E000000FE020000FE1FF000FE3FFC00FE603E00FE801F00FF801F80FF 000FC0FF000FC0FE000FE0FE000FE0FE000FE0FE000FE07E000FE07E000FE07E000FE07E 000FE03E000FE03F000FC01F000FC01F001F800F801F0007E07E0003FFFC0001FFF80000 3FC0001B277DA622>I<380000003E0000003FFFFFF03FFFFFF03FFFFFF07FFFFFE07FFF FFC07FFFFF807FFFFF0070000E0070000E0070001C00E0003800E0007000E000E0000001 C0000001C000000380000007800000070000000F0000001F0000001E0000003E0000003E 0000007E0000007C0000007C000000FC000000FC000000FC000000FC000001FC000001FC 000001FC000001FC000001FC000001FC000001FC000000F80000007000001C297CA822> I<003FC00001FFF00003FFFC0007C07E000F003F001E001F001E000F803E000F803E000F 803F000F803F800F803FC00F003FF01F001FFC1E001FFE3C000FFFF80007FFE00003FFF0 0001FFFC0001FFFE0007FFFF000F0FFF801E07FFC03E01FFC07C007FE07C001FE0F8000F E0F80007E0F80003E0F80003E0F80003E0F80003C07C0003C07E0007803F000F001FC03F 000FFFFC0003FFF800007FC0001B277DA622>I<007F800001FFF00007FFF8000FC0FC00 1F803E003F001F007E001F807E001F807E000F80FE000FC0FE000FC0FE000FC0FE000FE0 FE000FE0FE000FE0FE000FE0FE000FE07E001FE07E001FE03F003FE01F002FE00F80CFE0 07FF8FE001FF0FE000080FE000000FC000000FC000000FC000001F803E001F807F001F80 7F003F007F003E007F007E007E00FC003E03F8001FFFE0000FFF800001FE00001B277DA6 22>I<00000780000000000780000000000FC0000000000FC0000000000FC0000000001F E0000000001FE0000000003FF0000000003FF0000000003FF00000000077F80000000077 F800000000F7FC00000000E3FC00000000E3FC00000001C1FE00000001C1FE00000003C1 FF0000000380FF0000000380FF00000007007F80000007007F8000000F007FC000000E00 3FC000000E003FC000001C001FE000001C001FE000003FFFFFF000003FFFFFF000003FFF FFF00000700007F80000700007F80000F00007FC0000E00003FC0001E00003FE0001C000 01FE0001C00001FE0003C00001FF00FFFE003FFFFCFFFE003FFFFCFFFE003FFFFC2E297E A833>65 D<00007FE0030007FFFC07001FFFFF0F007FF00F9F00FF0001FF01FC0000FF03 F800007F07F000003F0FE000001F1FC000001F1FC000000F3F8000000F3F800000077F80 0000077F800000077F00000000FF00000000FF00000000FF00000000FF00000000FF0000 0000FF00000000FF00000000FF00000000FF000000007F000000007F800000007F800000 073F800000073F800000071FC00000071FC000000E0FE000000E07F000001C03F800003C 01FC00007800FF0001F0007FF007C0001FFFFF800007FFFE0000007FF00028297CA831> 67 DI73 D76 DI80 D82 D<00FF806003FFF0E00FFFF8E01F80FDE03F001FE03E0007E07C0003E07C0003E0FC 0001E0FC0001E0FC0000E0FE0000E0FE0000E0FF000000FFC000007FFC00007FFFE0003F FFF8001FFFFE001FFFFF0007FFFF8003FFFFC000FFFFC0000FFFE000007FE000001FF000 000FF0000007F0E00003F0E00003F0E00003F0E00003F0F00003E0F00003E0F80007E0FC 0007C0FF000F80FFE03F80E3FFFE00E1FFFC00C01FF0001C297CA825>I<7FFFFFFFFF80 7FFFFFFFFF807FFFFFFFFF807F807F807F807C007F800F8078007F80078078007F800780 70007F800380F0007F8003C0F0007F8003C0E0007F8001C0E0007F8001C0E0007F8001C0 E0007F8001C0E0007F8001C000007F80000000007F80000000007F80000000007F800000 00007F80000000007F80000000007F80000000007F80000000007F80000000007F800000 00007F80000000007F80000000007F80000000007F80000000007F80000000007F800000 00007F80000000007F80000000007F80000000007F80000000007F80000000007F800000 00FFFFFFC00000FFFFFFC00000FFFFFFC0002A287EA72F>I<03FF80000FFFF0001F01FC 003F80FE003F807F003F803F003F803F801F003F8000003F8000003F8000003F8000003F 80003FFF8001FC3F800FE03F801F803F803F003F807E003F80FC003F80FC003F80FC003F 80FC003F80FC005F807E00DF803F839FFC1FFE0FFC03FC03FC1E1B7E9A21>97 DI<003FF000 01FFFC0003F03E000FC07F001F807F003F007F003F007F007F003E007E0000007E000000 FE000000FE000000FE000000FE000000FE000000FE000000FE0000007E0000007E000000 7F0000003F0003803F8003801F8007000FE00E0003F83C0001FFF800003FC000191B7E9A 1E>I<00007FF000007FF000007FF0000007F0000007F0000007F0000007F0000007F000 0007F0000007F0000007F0000007F0000007F0000007F0000007F0003F87F001FFF7F007 F03FF00FC00FF01F8007F03F0007F03F0007F07E0007F07E0007F07E0007F0FE0007F0FE 0007F0FE0007F0FE0007F0FE0007F0FE0007F0FE0007F0FE0007F07E0007F07E0007F03F 0007F03F0007F01F800FF00FC01FF007E07FFF01FFE7FF007F87FF202A7EA925>I<003F C00001FFF00003E07C000F803E001F801F001F001F003F000F807E000F807E000FC07E00 0FC0FE0007C0FE0007C0FFFFFFC0FFFFFFC0FE000000FE000000FE0000007E0000007E00 00007F0000003F0001C01F0001C00F80038007C0070003F01E0000FFFC00003FE0001A1B 7E9A1F>I<0007F8003FFC007E3E01FC7F03F87F03F07F07F07F07F03E07F00007F00007 F00007F00007F00007F00007F000FFFFC0FFFFC0FFFFC007F00007F00007F00007F00007 F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007 F00007F00007F00007F00007F0007FFF807FFF807FFF80182A7EA915>I<00FF80F003FF E3F80FC1FE1C1F007C7C3F007E7C3E003E107E003F007E003F007E003F007E003F007E00 3F007E003F003E003E003F007E001F007C000FC1F8000BFFE00018FF8000180000003800 0000380000003C0000003FFFF8003FFFFF001FFFFFC00FFFFFE007FFFFF01FFFFFF03C00 07F07C0001F8F80000F8F80000F8F80000F8F80000F87C0001F07C0001F03F0007E00FC0 1F8007FFFF00007FF0001E287E9A22>I<07000F801FC03FE03FE03FE01FC00F80070000 00000000000000000000000000FFE0FFE0FFE00FE00FE00FE00FE00FE00FE00FE00FE00F E00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE0FFFEFFFEFFFE0F2B7EAA12 >105 D108 DII<003FE00001FFFC0003F07E000FC01F801F800FC03F0007E0 3F0007E07E0003F07E0003F07E0003F0FE0003F8FE0003F8FE0003F8FE0003F8FE0003F8 FE0003F8FE0003F8FE0003F87E0003F07E0003F03F0007E03F0007E01F800FC00FC01F80 07F07F0001FFFC00003FE0001D1B7E9A22>II114 D<03FE300FFFF03E03F07800F07000F0F0 0070F00070F80070FE0000FFE0007FFF007FFFC03FFFE01FFFF007FFF800FFF80007FC00 00FCE0007CE0003CF0003CF00038F80038FC0070FF01E0E7FFC0C1FF00161B7E9A1B>I< 00E00000E00000E00000E00001E00001E00001E00003E00003E00007E0000FE0001FFFE0 FFFFE0FFFFE00FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE000 0FE0000FE0000FE0000FE0700FE0700FE0700FE0700FE0700FE0700FE07007F0E003F0C0 01FF80007F0014267FA51A>IIIII E /Fs 1 51 df<1F0060C06060F070F030603000700070006000C001C00180020004000810101020 207FE0FFE00C137E9211>50 D E /Ft 9 118 df<01E307170C0F180F380E300E700E70 0EE01CE01CE01CE01CE039E039E0396079319A1E0C10127C9115>97 D<3F00070007000E000E000E000E001C001C001C001C0039E03A183C0C380C700C700E70 0E700EE01CE01CE01CE018E038E030E06060C031801E000F1D7C9C13>I<00F807040C04 18023804300470087FF0E000E000E000E000E00060046008301030600F800F127C9113> 101 D<01800380010000000000000000000000000000001C002600470047008E008E000E 001C001C001C0038003800710071007100720072003C00091C7C9B0D>105 D<1F800380038007000700070007000E000E000E000E001C001C001C001C003800380038 0038007000700070007000E200E200E200E40064003800091D7D9C0B>108 D<383E004CC3004D03804E03809E03809C03801C03801C0380380700380700380700380E 00700E40700E40701C40701C80E00C8060070012127C9117>110 D<1C3C2642468747078E068E000E000E001C001C001C001C003800380038003800700030 0010127C9112>114 D<01F006080C080C1C18181C001F001FC00FF007F0007800386030 E030C030806060C01F000E127D9111>I<1C01802E03804E03804E03808E07008E07001C 07001C0700380E00380E00380E00380E00301C80301C80301C80383C80184D000F860011 127C9116>117 D E /Fu 2 111 df<0FC00001C00001C000038000038000038000038000 0700000700000700000700000E07000E08800E11C00E23C01C47801C83001D00001E0000 3FC00038E000387000387000707100707100707100707200E03200601C00121D7E9C16> 107 D<3C1F004E61804681C04701C08F01C08E01C00E01C00E01C01C03801C03801C0380 1C0700380710380710380E10380E2070064030038014127E9119>110 D E /Fv 45 123 df<003F800000E0E0000380380007001C000E000E001C0007003C0007 8038000380780003C0780003C0700001C0F00001E0F10011E0F1FFF1E0F1FFF1E0F1FFF1 E0F10011E0F00001E0F00001E0700001C0780003C0780003C0380003803C0007801C0007 000E000E0007001C000380380000E0E000003F80001B1E7E9C20>2 D<007F000003C1E000070070001C001C003C001E0038000E0078000F0070000700F00007 80F0000780F0000780F0000780F00007807000070078000F0078000F0038000E001C001C 001C001C000E00380006003000060030008300608081004080810040804180C1007F80FF 007F80FF007F80FF00191D7E9C1E>10 D<007E0001C1800301800703C00E03C00E01800E 00000E00000E00000E00000E0000FFFFC00E01C00E01C00E01C00E01C00E01C00E01C00E 01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C07F87F8151D809C 17>12 D<00800100020006000C000C00180018003000300030006000600060006000E000 E000E000E000E000E000E000E000E000E000E000E0006000600060006000300030003000 180018000C000C000600020001000080092A7C9E10>40 D<800040002000300018001800 0C000C000600060006000300030003000300038003800380038003800380038003800380 03800380038003000300030003000600060006000C000C00180018003000200040008000 092A7E9E10>I<60F0F0701010101020204080040C7C830C>44 DI<60F0F06004047C830C>I<60F0F0600000000000000000000060F0F06004127C910C> 58 D<000600000006000000060000000F0000000F0000000F0000001780000017800000 37C0000023C0000023C0000043E0000041E0000041E0000080F0000080F0000080F00001 0078000100780001FFF80002003C0002003C0002003C0004001E0004001E000C001F000C 000F001E001F00FF00FFF01C1D7F9C1F>65 D<001F808000E0618001801980070007800E 0003801C0003801C00018038000180780000807800008070000080F0000000F0000000F0 000000F0000000F0000000F0000000F0000000F000000070000080780000807800008038 0000801C0001001C0001000E000200070004000180080000E03000001FC000191E7E9C1E >67 DI70 D73 D77 D80 D82 D<07E0801C1980300580300380600180E00180E00080E00080E00080F00000F8 00007C00007FC0003FF8001FFE0007FF0000FF80000F800007C00003C00001C08001C080 01C08001C0C00180C00180E00300D00200CC0C0083F800121E7E9C17>I<7FFFFFC0700F 01C0600F00C0400F0040400F0040C00F0020800F0020800F0020800F0020000F0000000F 0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F 0000000F0000000F0000000F0000000F0000000F0000000F0000001F800003FFFC001B1C 7F9B1E>I87 D<1FC000307000783800781C00301C00001C00001C0001 FC000F1C00381C00701C00601C00E01C40E01C40E01C40603C40304E801F870012127E91 15>97 DI<03F80C0C181E301E700C 6000E000E000E000E000E000E00060007002300218040C1803E00F127F9112>I<001F80 00038000038000038000038000038000038000038000038000038000038003F3800E0B80 180780300380700380600380E00380E00380E00380E00380E00380E00380600380700380 3003801807800E1B8003E3F0141D7F9C17>I<07E00C301818300C700E6006E006FFFEE0 00E000E000E00060007002300218040C1803E00F127F9112>I<00F8018C071E061E0E0C 0E000E000E000E000E000E00FFE00E000E000E000E000E000E000E000E000E000E000E00 0E000E000E000E000E007FE00F1D809C0D>I<00038007C4C01C78C0383880301800701C 00701C00701C00701C003018003838001C700027C0002000002000003000003FF8001FFF 001FFF802003806001C0C000C0C000C0C000C06001803003001C0E0007F800121C7F9215 >II<18003C003C00180000000000 00000000000000000000FC001C001C001C001C001C001C001C001C001C001C001C001C00 1C001C001C001C00FF80091D7F9C0C>I107 DIII<03F0000E1C00180600300300700380600180E001C0E001C0 E001C0E001C0E001C0E001C06001807003803003001806000E1C0003F00012127F9115> II<03E0800E1980180580380780700380700380E00380E0 0380E00380E00380E00380E003807003807003803807801807800E1B8003E38000038000 0380000380000380000380000380000380001FF0141A7F9116>II<1F90 20704030C010C010E010F8007F803FE00FF000F880388018C018C018E010D0608FC00D12 7F9110>I<04000400040004000C000C001C003C00FFE01C001C001C001C001C001C001C 001C001C001C101C101C101C101C100C100E2003C00C1A7F9910>IIIIII<7FFC70386038407040F040E041C003C0038007000F 040E041C043C0C380870087038FFF80E127F9112>I E /Fw 7 117 df<00038000000380000007C0000007C0000007C000000FE000000FE000001FF000001B F000003BF8000031F8000031F8000060FC000060FC0000E0FE0000C07E0000C07E000180 3F0001FFFF0003FFFF8003001F8007001FC006000FC006000FC00C0007E00C0007E0FF80 3FFEFF803FFE1F1C7E9B24>65 D<0FF8001C1E003E0F803E07803E07C01C07C00007C000 7FC007E7C01F07C03C07C07C07C0F807C0F807C0F807C0780BC03E13F80FE1F815127F91 17>97 DI<03FC000E0E001C1F003C 1F00781F00780E00F80000F80000F80000F80000F80000F800007800007801803C01801C 03000E0E0003F80011127E9115>I114 D<1FD830786018E018E018F000FF807FE07FF01FF807FC007CC01CC01CE01C E018F830CFC00E127E9113>I<0300030003000300070007000F000F003FFCFFFC1F001F 001F001F001F001F001F001F001F001F0C1F0C1F0C1F0C0F08079803F00E1A7F9913>I E /Fx 16 122 df<3078FCFC7830060676851A>46 D<003E0001FF8003FFC007C1E00F00 E01E0F703C3FF0387FF07070F870E07870E078E1C038E1C038E1C038E1C038E1C038E1C0 38E1C038E1C03870E07070E0707070E0387FE03C3FC01E0F000F003807C0F803FFF001FF E0003F00151E7E9D1A>64 D<1FF0003FFC007FFE00780F00300700000380000380007F80 07FF801FFF803F8380780380700380E00380E00380E00380700780780F803FFFFC1FFDFC 07F0FC16157D941A>97 D<00FF8003FFC00FFFE01F01E03C00C0780000700000700000E0 0000E00000E00000E00000E000007000007000007800703C00701F01F00FFFE003FFC000 FE0014157D941A>99 D<000FC0001FC0000FC00001C00001C00001C00001C00001C00001 C001F1C007FDC00FFFC01E0FC03C07C07803C07001C0E001C0E001C0E001C0E001C0E001 C0E001C0E001C07003C07003C03807C03E0FC01FFFF807FDFC01F1F8161E7E9D1A>I<01 F80007FF000FFF801E07C03C01C07800E07000E0E00070E00070FFFFF0FFFFF0FFFFF0E0 00007000007000007800703C00701F01F00FFFE003FF8000FE0014157D941A>I<0007E0 001FF0003FF800787800F03000E00000E00000E00000E0007FFFF0FFFFF0FFFFF000E000 00E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E000 00E00000E0003FFF807FFFC03FFF80151E7F9D1A>I<00C00001E00001E00000C0000000 000000000000000000000000000000007FE0007FE0007FE00000E00000E00000E00000E0 0000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E0007FFF 80FFFFC07FFF80121F7C9E1A>105 D107 D<7E3E00FEFF807FFFC00FC1C00F80E00F00E00E00E00E00E00E00E00E00 E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E07FC3FCFFE7FE7FC3FC1715 7F941A>110 D<01F00007FC001FFF003E0F803C07807803C07001C0E000E0E000E0E000 E0E000E0E000E0E000E0F001E07001C07803C03C07803E0F801FFF0007FC0001F0001315 7D941A>I<7F81F8FF8FFC7F9FFE03FE1E03F80C03E00003E00003C00003800003800003 80000380000380000380000380000380000380000380007FFF00FFFF007FFF0017157F94 1A>114 D<07FB801FFF807FFF80780780E00380E00380E003807800007FC0001FFC0007 FE00003F800007806001C0E001C0E001C0F003C0FC0780FFFF00EFFE00E3F80012157C94 1A>I<0180000380000380000380000380000380000380007FFFE0FFFFE0FFFFE0038000 038000038000038000038000038000038000038000038000038000038070038070038070 03807001C1E001FFE000FF80003F00141C7F9B1A>I<7E07E0FE0FE07E07E00E00E00E00 E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E01 E00F03E007FFFC03FFFE00FCFC17157F941A>I<7F83FCFFC7FE7F83FC0E00E00E00E007 00E00701C00701C00381C003838003C38001C38001C70000E70000E70000E60000660000 6E00003C00003C00003C0000380000380000380000700000700030F00078E00071E0007F C0003F80001E000017207F941A>121 D E /Fy 33 122 df<0020004000800100030006 0004000C000C00180018003000300030007000600060006000E000E000E000E000E000E0 00E000E000E000E000E000E000E000E0006000600060007000300030003000180018000C 000C0004000600030001000080004000200B327CA413>40 D<800040002000100018000C 000400060006000300030001800180018001C000C000C000C000E000E000E000E000E000 E000E000E000E000E000E000E000E000E000C000C000C001C00180018001800300030006 00060004000C00180010002000400080000B327DA413>I<70F8FCFC7404040404080810 102040060F7C840E>44 DI<01F000071C000C06001803003803 803803807001C07001C07001C07001C0F001E0F001E0F001E0F001E0F001E0F001E0F001 E0F001E0F001E0F001E0F001E0F001E0F001E0F001E07001C07001C07001C07803C03803 803803801C07000C0600071C0001F00013227EA018>48 D<008003800F80F38003800380 038003800380038003800380038003800380038003800380038003800380038003800380 038003800380038003800380038007C0FFFE0F217CA018>I<03F0000C1C001007002007 804003C04003C08003E0F003E0F801E0F801E0F801E02003E00003E00003C00003C00007 80000700000E00001C0000180000300000600000C0000180000100000200200400200800 201800603000403FFFC07FFFC0FFFFC013217EA018>I<03F8000C1E00100F0020078040 07C07807C07803C07807C03807C0000780000780000700000F00000C0000380003F00000 1C00000F000007800007800003C00003C00003E02003E07003E0F803E0F803E0F003C040 03C0400780200780100F000C1C0003F00013227EA018>I<000300000300000700000700 000F00001700001700002700006700004700008700018700010700020700060700040700 080700080700100700200700200700400700C00700FFFFF8000700000700000700000700 000700000700000700000F80007FF015217FA018>I<1000801E07001FFF001FFE001FF8 0017E00010000010000010000010000010000010000011F800120C001C07001803801003 800001C00001C00001E00001E00001E00001E07001E0F001E0F001E0E001C08001C04003 C04003802007001006000C1C0003F00013227EA018>I<007E0001C1000300800601C00C 03C01C03C0180180380000380000780000700000700000F0F800F30C00F40600F40300F8 0380F801C0F001C0F001E0F001E0F001E0F001E0F001E07001E07001E07001E03801C038 01C01803801C03000C0600070C0001F00013227EA018>I<4000006000007FFFE07FFFC0 7FFFC0400080C00100800100800200800200000400000800000800001000002000002000 00600000400000C00000C00001C00001C000018000038000038000038000038000078000 07800007800007800007800007800007800003000013237DA118>I<0007E01000381830 00E0063001C00170038000F0070000F00E0000701E0000701C0000303C0000303C000030 7C0000107800001078000010F8000000F8000000F8000000F8000000F8000000F8000000 F8000000F800000078000000780000107C0000103C0000103C0000101C0000201E000020 0E000040070000400380008001C0010000E0020000381C000007E0001C247DA223>67 DI< 03FFE0001F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00 000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00 000F00000F00700F00F80F00F80F00F80E00F01E00401C0020380018700007C00013237E A119>74 D<03F0200C0C601802603001E07000E0600060E00060E00060E00020E00020E0 0020F00000F000007800007F00003FF0001FFE000FFF0003FF80003FC00007E00001E000 00F00000F0000070800070800070800070800070C00060C00060E000C0F000C0C80180C6 070081FC0014247DA21B>83 D85 D<1FE000303800780C00780E0030070000070000 070000070000FF0007C7001E07003C0700780700700700F00708F00708F00708F00F0878 17083C23900FC1E015157E9418>97 D<01FE000703000C07801C07803803007800007000 00F00000F00000F00000F00000F00000F00000F000007000007800403800401C00800C01 0007060001F80012157E9416>99 D<0000E0000FE00001E00000E00000E00000E00000E0 0000E00000E00000E00000E00000E00000E00000E001F8E00704E00C02E01C01E03800E0 7800E07000E0F000E0F000E0F000E0F000E0F000E0F000E0F000E07000E07800E03800E0 1801E00C02E0070CF001F0FE17237EA21B>I<01FC000707000C03801C01C03801C07801 E07000E0F000E0FFFFE0F00000F00000F00000F00000F000007000007800203800201C00 400E008007030000FC0013157F9416>I<003E0000E30001C78003878003078007000007 0000070000070000070000070000070000070000070000FFF80007000007000007000007 000007000007000007000007000007000007000007000007000007000007000007000007 00000700000700000780007FF000112380A20F>I<1C003E003E003E001C000000000000 00000000000000000000000E007E001E000E000E000E000E000E000E000E000E000E000E 000E000E000E000E000E000E000E00FFC00A227FA10E>105 D<0E1FC07F00FE60E18380 1E807201C00F003C00E00F003C00E00E003800E00E003800E00E003800E00E003800E00E 003800E00E003800E00E003800E00E003800E00E003800E00E003800E00E003800E00E00 3800E00E003800E00E003800E00E003800E0FFE3FF8FFE27157F942A>109 D<0E1F80FE60C01E80E00F00700F00700E00700E00700E00700E00700E00700E00700E00 700E00700E00700E00700E00700E00700E00700E00700E0070FFE7FF18157F941B>I<01 FC000707000C01801800C03800E0700070700070F00078F00078F00078F00078F00078F0 0078F000787000707800F03800E01C01C00E038007070001FC0015157F9418>I<0E1F00 FE61C00E80600F00700E00380E003C0E003C0E001E0E001E0E001E0E001E0E001E0E001E 0E001E0E003C0E003C0E00380F00700E80E00E41C00E3F000E00000E00000E00000E0000 0E00000E00000E00000E00000E0000FFE000171F7F941B>I<0E3CFE461E8F0F0F0F060F 000E000E000E000E000E000E000E000E000E000E000E000E000E000F00FFF010157F9413 >114 D<0F8830786018C018C008C008E008F0007F003FE00FF001F8003C801C800C800C C00CC008E018D0308FC00E157E9413>I<02000200020002000600060006000E001E003E 00FFFC0E000E000E000E000E000E000E000E000E000E000E000E040E040E040E040E040E 040708030801F00E1F7F9E13>I<0E0070FE07F01E00F00E00700E00700E00700E00700E 00700E00700E00700E00700E00700E00700E00700E00700E00700E00F00E00F006017003 827800FC7F18157F941B>II121 D E /Fz 7 107 df0 D<020002000200C218F2783A E00F800F803AE0F278C2180200020002000D0E7E8E12>3 D<060F0F0E1E1E1C3C383830 707060E0C04008117F910A>48 D<01FF8007FF800E000018000030000060000060000060 0000C00000C00000FFFF80FFFF80C00000C000006000006000006000003000001800000E 000007FF8001FF8011167D9218>50 D<0003000300060006000C000C0018001800300030 0060006000C000C00180018003000300060006000C000C00180018003000300060006000 C0004000101E7B9600>54 D<03F8001FFF003C07806000C0C00060C00060C00060C00060 C00060C00060C00060C00060C00060C00060C00060C00060C00060C0006040002013137E 9218>92 D106 D E /FA 9 122 df100 D105 D107 D110 D<007F800001C0E000070038000E00 1C001C000E003C000F0038000700780007807000038070000380F00003C0F00003C0F000 03C0F00003C0F00003C0F00003C0F00003C07800078078000780380007003C000F001C00 0E000E001C000700380001C0E000007F80001A1A7E9920>II114 D<7FFFFF00701E0700601E0100401E0100C01E0180801E0080801E008080 1E0080001E0000001E0000001E0000001E0000001E0000001E0000001E0000001E000000 1E0000001E0000001E0000001E0000001E0000001E0000001E0000001E0000003F000003 FFF000191A7F991D>116 D121 D E /FB 22 118 df<0000007800000000000078 000000000000FC000000000000FC000000000000FC000000000001FE000000000001FE00 0000000003FF000000000003FF000000000007FF800000000007FF800000000007FF8000 0000000FFFC0000000000E7FC0000000001E7FE0000000001C3FE0000000001C3FE00000 0000383FF000000000381FF000000000781FF800000000700FF800000000700FF8000000 00E00FFC00000000E007FC00000001E007FE00000001C003FE00000001C003FE00000003 8001FF000000038001FF000000078001FF800000070000FF8000000F0000FFC000000FFF FFFFC000000FFFFFFFC000001FFFFFFFE000001C00003FE000003C00003FF00000380000 1FF000003800001FF000007000001FF800007000000FF80000F000000FFC0000E0000007 FC0000E0000007FC0001C0000007FE0003E0000003FE00FFFF0001FFFFFCFFFF0001FFFF FCFFFF0001FFFFFC36317DB03D>65 D77 D80 D<001FF8018000FFFF038003FFFFC78007F007EF800F 8000FF801F00007F803E00001F803E00000F807C00000F807C00000780FC00000780FC00 000780FC00000380FE00000380FE00000380FF00000000FFC00000007FF00000007FFF80 00003FFFF800003FFFFF80001FFFFFF0000FFFFFF80007FFFFFC0003FFFFFF0000FFFFFF 00003FFFFF800001FFFFC000001FFFE0000001FFE00000003FE00000001FF00000000FF0 00000007F060000007F0E0000003F0E0000003F0E0000003F0E0000003E0F0000003E0F0 000003E0F8000007C0FC000007C0FF00000F80FFC0001F00FBFC00FE00F1FFFFF800E03F FFF000C003FF800024317CB02D>83 D<7FFFFFFFFFFF007FFFFFFFFFFF007FFFFFFFFFFF 007FC00FF801FF007E000FF8003F007C000FF8001F0078000FF8000F0078000FF8000F00 70000FF8000700F0000FF8000780F0000FF8000780F0000FF8000780E0000FF8000380E0 000FF8000380E0000FF8000380E0000FF8000380E0000FF800038000000FF80000000000 0FF800000000000FF800000000000FF800000000000FF800000000000FF800000000000F F800000000000FF800000000000FF800000000000FF800000000000FF800000000000FF8 00000000000FF800000000000FF800000000000FF800000000000FF800000000000FF800 000000000FF800000000000FF800000000000FF800000000000FF800000000000FF80000 0000000FF800000000000FF800000000000FF800000000000FF800000000000FF8000000 00000FF8000000007FFFFFFF0000007FFFFFFF0000007FFFFFFF000031307DAF38>I<00 FFF0000003FFFF00000F803F80000FC00FE0001FE007F0001FE007F0001FE003F8000FC0 03FC00078003FC00000003FC00000003FC00000003FC00000003FC000000FFFC00001FFF FC0000FFE3FC0003FC03FC000FF003FC001FC003FC003FC003FC007F8003FC007F8003FC 00FF0003FC00FF0003FC00FF0003FC00FF0007FC00FF0007FC007F800DFC003FC01DFE00 1FE078FFF007FFE07FF000FF803FF024207E9F27>97 D<01F8000000FFF8000000FFF800 0000FFF80000000FF800000007F800000007F800000007F800000007F800000007F80000 0007F800000007F800000007F800000007F800000007F800000007F800000007F8000000 07F800000007F83FE00007F8FFFC0007FBE07F0007FF001F8007FE000FC007FC000FE007 F80007F007F80007F807F80007F807F80003FC07F80003FC07F80003FC07F80003FE07F8 0003FE07F80003FE07F80003FE07F80003FE07F80003FE07F80003FE07F80003FE07F800 03FC07F80003FC07F80003FC07F80007F807F80007F807F80007F007FC000FE007FE000F C007E7003F8007C3C0FE000780FFF80007003FC00027327EB12D>I<000FFF00007FFFC0 01FC01F003F003F007E007F80FE007F81FC007F83FC003F03FC001E07F8000007F800000 7F800000FF800000FF800000FF800000FF800000FF800000FF800000FF800000FF800000 7F8000007F8000007F8000003FC0001C3FC0001C1FC000380FE0003807E0007003F001E0 01FC07C0007FFF00000FF8001E207D9F24>I<000FFC00007FFF8001FC0FC003F003E007 E001F00FE001F81FC000FC3FC000FE3FC000FE7F80007E7F80007F7F80007FFF80007FFF 80007FFFFFFFFFFFFFFFFFFF800000FF800000FF800000FF8000007F8000007F8000007F 8000003FC000071FC000071FC0000E0FE0000E07F0001C03F8007800FE03E0003FFFC000 07FE0020207E9F25>101 D<0001FE00000FFF80001FC3C0007F07E000FE0FF001FE0FF0 01FC0FF003FC0FF003FC07E003FC018003FC000003FC000003FC000003FC000003FC0000 03FC000003FC000003FC0000FFFFFC00FFFFFC00FFFFFC0003FC000003FC000003FC0000 03FC000003FC000003FC000003FC000003FC000003FC000003FC000003FC000003FC0000 03FC000003FC000003FC000003FC000003FC000003FC000003FC000003FC000003FC0000 03FC000003FC000003FC000003FC000003FC00007FFFF0007FFFF0007FFFF0001C327EB1 19>I<001FF007C000FFFE3FE001F83F79F007E00FC3F00FE00FE1F00FC007E0E01FC007 F0001FC007F0003FC007F8003FC007F8003FC007F8003FC007F8003FC007F8001FC007F0 001FC007F0000FC007E0000FE00FE00007E00FC00003F83F000006FFFE00000E1FF00000 0E000000001E000000001E000000001F000000001F800000001FFFFF80000FFFFFF0000F FFFFFC0007FFFFFE0003FFFFFF0003FFFFFF800FFFFFFFC03F00007FC07E00001FE07C00 000FE0FC000007E0FC000007E0FC000007E0FC000007E07E00000FC03E00000F803F0000 1F800FC0007E0007F803FC0001FFFFF000001FFF0000242F7E9F28>I<01F8000000FFF8 000000FFF8000000FFF80000000FF800000007F800000007F800000007F800000007F800 000007F800000007F800000007F800000007F800000007F800000007F800000007F80000 0007F800000007F800000007F807F80007F83FFE0007F8783F0007F8C03F8007F9801FC0 07FB001FC007FE001FE007FC001FE007FC001FE007FC001FE007F8001FE007F8001FE007 F8001FE007F8001FE007F8001FE007F8001FE007F8001FE007F8001FE007F8001FE007F8 001FE007F8001FE007F8001FE007F8001FE007F8001FE007F8001FE007F8001FE007F800 1FE007F8001FE007F8001FE0FFFFC3FFFFFFFFC3FFFFFFFFC3FFFF28327DB12D>I<03C0 0007E0000FF0001FF8001FF8001FF8001FF8000FF00007E00003C0000000000000000000 0000000000000000000000000000000000000001F8007FF8007FF8007FF80007F80007F8 0007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F8 0007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F800FFFF 80FFFF80FFFF8011337DB217>I<01F800FFF800FFF800FFF8000FF80007F80007F80007 F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007 F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007 F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007 F80007F80007F80007F800FFFFC0FFFFC0FFFFC012327DB117>108 D<03F007F8001FE000FFF03FFE00FFF800FFF0783F01E0FC00FFF0C03F8300FE000FF180 1FC6007F0007F3001FCC007F0007F6001FF8007F8007FC001FF0007F8007FC001FF0007F 8007FC001FF0007F8007F8001FE0007F8007F8001FE0007F8007F8001FE0007F8007F800 1FE0007F8007F8001FE0007F8007F8001FE0007F8007F8001FE0007F8007F8001FE0007F 8007F8001FE0007F8007F8001FE0007F8007F8001FE0007F8007F8001FE0007F8007F800 1FE0007F8007F8001FE0007F8007F8001FE0007F8007F8001FE0007F8007F8001FE0007F 8007F8001FE0007F8007F8001FE0007F80FFFFC3FFFF0FFFFCFFFFC3FFFF0FFFFCFFFFC3 FFFF0FFFFC3E207D9F43>I<03F007F800FFF03FFE00FFF0783F00FFF0C03F800FF1801F C007F3001FC007F6001FE007FC001FE007FC001FE007FC001FE007F8001FE007F8001FE0 07F8001FE007F8001FE007F8001FE007F8001FE007F8001FE007F8001FE007F8001FE007 F8001FE007F8001FE007F8001FE007F8001FE007F8001FE007F8001FE007F8001FE007F8 001FE007F8001FE007F8001FE0FFFFC3FFFFFFFFC3FFFFFFFFC3FFFF28207D9F2D>I<00 07FC0000007FFFC00001FC07F00003F001F80007E000FC000FC0007E001FC0007F003FC0 007F803F80003F807F80003FC07F80003FC07F80003FC0FF80003FE0FF80003FE0FF8000 3FE0FF80003FE0FF80003FE0FF80003FE0FF80003FE0FF80003FE07F80003FC07F80003F C07F80003FC03FC0007F803FC0007F801FC0007F000FE000FE0007E000FC0003F803F800 01FE0FF000007FFFC0000007FC000023207E9F28>I<01F83FE000FFF8FFFC00FFFBE07F 00FFFF003F8007FE001FC007FC000FE007F8000FF007F80007F807F80007F807F80007FC 07F80003FC07F80003FC07F80003FE07F80003FE07F80003FE07F80003FE07F80003FE07 F80003FE07F80003FE07F80003FE07F80003FC07F80007FC07F80007FC07F80007F807F8 0007F807F8000FF007FC000FE007FE001FC007FF003F8007FBC0FE0007F8FFF80007F83F C00007F800000007F800000007F800000007F800000007F800000007F800000007F80000 0007F800000007F800000007F800000007F8000000FFFFC00000FFFFC00000FFFFC00000 272E7E9F2D>I<03F03F00FFF07FC0FFF1C3E0FFF187E00FF30FF007F60FF007F60FF007 FC07E007FC03C007FC000007FC000007F8000007F8000007F8000007F8000007F8000007 F8000007F8000007F8000007F8000007F8000007F8000007F8000007F8000007F8000007 F8000007F8000007F8000007F80000FFFFE000FFFFE000FFFFE0001C207E9F21>114 D<01FF860007FFFE001F00FE003C003E0078001E0078000E00F8000E00F8000E00F8000E 00FC000000FF800000FFFC00007FFFC0003FFFF0003FFFF8001FFFFC0007FFFE0001FFFF 00003FFF000000FF8000003F8060001F80E0000F80E0000F80F0000F80F0000F00F8000F 00FC001E00FE001C00FF807800F3FFF000C07F800019207D9F20>I<001C0000001C0000 001C0000001C0000001C0000003C0000003C0000003C0000007C0000007C000000FC0000 01FC000003FC000007FC00001FFFFE00FFFFFE00FFFFFE0003FC000003FC000003FC0000 03FC000003FC000003FC000003FC000003FC000003FC000003FC000003FC000003FC0000 03FC000003FC000003FC000003FC000003FC038003FC038003FC038003FC038003FC0380 03FC038003FC038001FC038001FC070000FE0700007F0E00003FFC000007F000192E7FAD 1F>I<01F80007E0FFF803FFE0FFF803FFE0FFF803FFE00FF8003FE007F8001FE007F800 1FE007F8001FE007F8001FE007F8001FE007F8001FE007F8001FE007F8001FE007F8001F E007F8001FE007F8001FE007F8001FE007F8001FE007F8001FE007F8001FE007F8001FE0 07F8001FE007F8001FE007F8001FE007F8003FE007F8003FE003F8007FE003F8007FE001 FC00DFF000FE039FFF007FFF1FFF000FFC1FFF28207D9F2D>I E end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%EndSetup %%Page: 1 1 1 0 bop 5 228 a FB(Sublinear)26 b(Time)g(Algorithms)h(for)g(Metric)e (Space)i(Problems)820 354 y FA(piotr)19 b(ind)o(yk)1130 336 y Fz(\003)647 412 y Fy(Computer)c(Science)g(Departmen)o(t)766 470 y(Stanford)i(Univ)o(ersit)o(y)818 529 y(\(650\)-723-453)q(2)706 587 y Fx(indyk@cs.s)o(ta)o(nfo)o(rd.)o(edu)828 688 y Fy(June)g(21,)f(2000)884 905 y Fw(Abstract)176 981 y Fv(In)c(this)h(pap)q(er)g(w)o(e)g(giv)o(e)f(appro)o(ximation)d (algorithms)i(for)h(the)h(follo)o(wing)d(problems)h(on)h(metric)g (spaces:)114 1031 y(F)m(urthest)h(P)o(air,)e Fu(k)q Fv(-median,)f (Minim)o(um)e(Routing)j(Cost)h(Spanning)f(T)m(ree,)i(Multiple)e (Sequence)j(Alignmen)o(t,)114 1081 y(Maxim)o(um)d(T)m(ra)o(v)o(eling)i (Salesman)g(Problem,)g(Maxim)o(um)f(Spanning)i(T)m(ree)h(and)g(Av)o (erage)g(Distance.)21 b(The)114 1131 y(k)o(ey)13 b(prop)q(ert)o(y)h(of) f(our)g(algorithms)e(is)i(that)h(their)f(running)g(times)g(is)g Ft(line)n(ar)f Fv(in)h(the)h(n)o(um)o(b)q(er)e(of)h(p)q(oin)o(ts.)18 b(As)114 1180 y(the)11 b(full)f(sp)q(eci\014cation)h(of)g(an)f Fu(n)p Fv(-p)q(oin)o(t)h(metric)f(space)i(is)f(of)f(size)i(\002\()p Fu(n)1195 1165 y Fs(2)1214 1180 y Fv(\),)f(the)g(complexit)o(y)e(of)i (our)g(algorithms)114 1230 y(is)k Ft(subline)n(ar)g Fv(with)f(resp)q (ect)k(to)d(the)h(input)f(size.)22 b(All)15 b(previous)g(algorithms)e (\(exact)j(or)f(appro)o(ximate\))f(for)114 1280 y(these)g(problems)d (ha)o(v)o(e)i(running)f(times)g(\012\()p Fu(n)824 1265 y Fs(2)842 1280 y Fv(\).)18 b(W)m(e)12 b(b)q(eliev)o(e)h(that)g(our)g (tec)o(hniques)g(can)g(b)q(e)h(applied)e(to)g(get)114 1330 y(similar)f(b)q(ounds)j(for)g(other)g(problems.)0 1473 y Fr(1)67 b(In)n(tro)r(duction)0 1574 y Fq(In)19 b(recen)o(t)f(y)o(ears)f(there)h(has)g(b)q(een)h(a)f(dramatic)g(gro)o (wth)e(of)i(in)o(terest)g(in)h(algorithms)f(op)q(erating)g(on)g(massiv) o(e)0 1631 y(data)e(sets.)24 b(This)18 b(p)q(oses)f(new)g(c)o (hallenges)h(for)e(algorithm)h(design,)h(as)e(algorithms)h(whic)o(h)g (are)g(quite)g(e\016cien)o(t)0 1687 y(on)f(small)g(inputs)h(\(for)e (example,)i(ha)o(ving)f(quadratic)g(running)h(time\))f(can)g(b)q(ecome) g(prohibitiv)o(ely)i(exp)q(ensiv)o(e)0 1744 y(for)13 b(input)i(sizes)g(of,)e(sa)o(y)l(,)h(sev)o(eral)g(gigab)o(ytes.)19 b(F)l(ortunately)l(,)14 b(applications)h(lik)o(e)g(similarit)o(y)g (searc)o(h,)f(clustering,)0 1800 y(data)i(visualisation)i(and)f (represen)o(tation)g([8)o(])g(often)f(demand)h(answ)o(ers)f(whic)o(h)i (are)e(not)h(necessarily)h(en)o(tirely)0 1857 y(accurate)13 b(or)h(complete.)20 b(This)14 b(mak)o(es)f(appro)o(ximate)g (computation)h(a)f(promising)i(to)q(ol)e(for)g(coping)i(with)f(large)0 1913 y(data)h(sizes.)71 1970 y(There)21 b(w)o(as)f(a)g(lot)h(of)f (recen)o(t)h(algorithmic)h(researc)o(h)f(along)f(these)h(lines.)39 b(This)21 b(includes)i(researc)o(h)e(on)0 2026 y(appro)o(ximate)d (nearest)h(neigh)o(b)q(or)h([5)o(,)e(15,)g(13,)g(16,)g(12)o(,)h(1])f (whic)o(h)i(sho)o(ws)e(that)g(e\016cien)o(t)i(algorithms)e(can)h(b)q(e) 0 2083 y(designed)k(ev)o(en)f(for)f(large)g(high)i(dimensional)g(data)e (sets.)39 b(In)22 b(particular,)h(the)f(results)g(of)f([13)o(,)g(12)o (])h(sho)o(w)0 2139 y(that)e(almost)g(linear)i(time/space)f(algorithms) f(can)h(b)q(e)g(designed)h(for)e(appro)o(ximate)g(pro)o(ximit)o(y)h (problems,)0 2195 y(e.g.,)d(\014nding)i(near\(est\))e(p)q(oin)o(ts,)i (closest)f(pair)g(of)f(p)q(oin)o(ts,)i(minim)o(um)g(spanning)g(tree)e (or)g(other)h(v)m(arian)o(ts)f(of)0 2252 y(hierarc)o(hical)h (clustering)f(\(cf.)f([1)o(]\).)25 b(Unfortunately)l(,)18 b(these)f(algorithms)g(are)g(restricted)g(to)g(sp)q(eci\014c)i (\(usually)0 2308 y(geometric\))d(metric)g(spaces,)g(making)h(them)f (unsuitable)i(for)d(non-geometric)i(ones)f(lik)o(e)h(edit)g(distance)g (\(used)0 2365 y(in)f(molecular)g(biology\))f(or)g(other)f(domain-sp)q (eci\014c)k(measures.)i(It)15 b(is)g(therefore)g(desirable)h(to)f (consider)h(these)0 2421 y(problems)g(in)g(general)g(metric)f(spaces.) 71 2478 y(In)i(this)f(pap)q(er)h(w)o(e)f(address)h(these)f(issues)i(b)o (y)e(pro)o(viding)h(appro)o(ximation)g(algorithms)f(for)g(the)g(follo)o (wing)0 2534 y(metric)g(space)g(problems:)22 b Fp(k)q Fq(-median,)16 b(Minim)o(um)h(Routing)f(Cost)f(Spanning)i(T)l(ree)f (\(MR)o(CST\)/Multiple)g(Se-)0 2591 y(quence)d(Alignmen)o(t)h(\(MSA\),) d(Maxim)o(um)h(T)l(ra)o(v)o(eling)h(Salesman)g(Problem)g(\(MaxTSP\),)e (Maxim)o(um)h(Spanning)p 0 2633 780 2 v 51 2660 a Fo(\003)69 2676 y Fn(Supp)q(orted)j(b)o(y)e(Stanford)h(Graduate)g(F)m(ello)o (wship)i(and)d(NSF)g(Gran)o(t)h(I)q(IS-9811904)964 2825 y Fq(1)p eop %%Page: 2 2 2 1 bop 19 2 1912 2 v 19 10 V 18 66 2 57 v 27 66 V 53 49 a Fq(problem)p 338 66 V 150 w(running)16 b(time)p 645 66 V 50 w(appro)o(ximation)f(factor)p 1113 66 V 49 w(output)p 1484 66 V 237 w(ob)s(jectiv)o(e)p 1922 66 V 1931 66 V 19 68 1912 2 v 18 125 2 57 v 27 125 V 53 108 a(F)l(urthest)f(pair)p 338 125 V 51 w Fp(O)q Fq(\()p Fp(n)p Fq(\))p 645 125 V 676 90 a Fm(1)p 676 97 18 2 v 676 123 a(2)p 1113 125 2 57 v 1139 108 a Fq(p)q(oin)o(ts)i Fp(p;)8 b(q)p 1484 125 V 170 w Fq(max)f Fp(d)p Fq(\()p Fp(p;)h(q)r Fq(\))p 1922 125 V 1931 125 V 18 184 2 60 v 27 184 V 53 166 a Fp(k)q Fq(-median)p 338 184 V 374 155 a(~)364 166 y Fp(O)q Fq(\()p Fp(nk)q(=\016)515 150 y Fm(2)534 166 y Fq(\))p 645 184 V 119 w([\(1)h(+)i Fp(\016)r Fq(\)\(2)e(+)h(4)p Fp(\013)p Fq(\))p Fp(;)e Fq(2)p Fp(\014)r Fq(])p 1113 184 V 69 w(p)q(oin)o(ts)16 b Fp(c)1296 173 y Fm(1)1323 166 y Fp(:)8 b(:)g(:)d(c)1403 173 y Fl(k)p 1484 184 V 1510 166 a Fq(min)1593 134 y Fk(P)1637 178 y Fl(p)1664 166 y Fq(min)1740 173 y Fl(i)1762 166 y Fp(d)p Fq(\()p Fp(p;)j(c)1868 173 y Fl(i)1880 166 y Fq(\))p 1922 184 V 1931 184 V 18 241 2 57 v 27 241 V 53 224 a(1-median)p 338 241 V 130 w Fp(O)q Fq(\()p Fp(n=\016)490 207 y Fm(5)509 224 y Fq(\))p 645 241 V 144 w(1)i(+)g Fp(\016)p 1113 241 V 1484 241 V 1922 241 V 1931 241 V 18 297 V 27 297 V 53 280 a Fq(MaxTSP)p 338 297 V 133 w Fp(O)q Fq(\()p Fp(n=\016)r Fq(\))p 645 297 V 676 262 a Fm(1)p 676 269 18 2 v 676 296 a(2)709 280 y Fj(\000)g Fp(\016)p 1113 297 2 57 v 365 w Fq(a)15 b(tour)g Fp(T)p 1484 297 V 207 w Fq(max)1602 248 y Fk(P)1646 292 y Fl(e)p Fz(2)p Fl(T)1721 280 y Fp(d)p Fq(\()p Fp(e)p Fq(\))p 1922 297 V 1931 297 V 18 356 2 59 v 27 356 V 53 339 a(MaxST)p 338 356 V 374 328 a(~)364 339 y Fp(O)q Fq(\()p Fp(n=\016)r Fq(\))p 645 356 V 676 321 a Fm(1)p 676 328 18 2 v 676 355 a(2)709 339 y Fj(\000)10 b Fp(\016)p 1113 356 2 59 v 365 w Fq(a)15 b(tree)g Fp(T)p 1484 356 V 215 w Fq(max)1602 307 y Fk(P)1646 351 y Fl(e)p Fz(2)p Fl(T)1721 339 y Fp(d)p Fq(\()p Fp(e)p Fq(\))p 1922 356 V 1931 356 V 18 413 2 58 v 27 413 V 53 396 a(MR)o(CST)p 338 413 V 146 w Fp(O)q Fq(\()p Fp(n=\016)r Fq(\))p 645 413 V 163 w(2)10 b(+)g Fp(\016)p 1113 413 V 370 w Fq(a)15 b(tree)g Fp(T)p 1484 413 V 215 w Fq(min)1593 363 y Fk(P)1637 407 y Fl(p;q)1691 396 y Fp(d)1715 403 y Fl(T)1742 396 y Fq(\()p Fp(p;)8 b(q)r Fq(\))p 1922 413 V 1931 413 V 18 494 2 81 v 27 494 V 53 455 a(AvgD)p 338 494 V 195 w Fp(O)q Fq(\()p Fp(n=\016)490 438 y Fm(7)p Fl(=)p Fm(2)544 455 y Fq(\))p 645 494 V 109 w(1)i(+)g Fp(\016)p 1113 494 V 1176 437 a Fm(1)p 1144 444 82 2 v 1144 483 a Fq(\()1162 465 y Fo(j)p Fi(X)r Fo(j)1177 493 y Fh(2)1208 483 y Fq(\))1238 423 y Fk(P)1282 466 y Fl(p;q)1336 455 y Fp(d)p Fq(\()p Fp(p;)e(q)r Fq(\))p 1484 494 2 81 v 1922 494 V 1931 494 V 19 496 1912 2 v 0 576 a(T)l(able)17 b(1:)k(The)c(result)f(table.)23 b(The)16 b(notation)g([)p Fp(a;)8 b(b)p Fq(])14 b(means)i(the)g(algorithm)g (returns)g Fp(bk)h Fq(median)g(with)f(cost)g Fp(a)0 632 y Fq(times)e(the)g(optimal)g Fp(k)q Fq(-median)h(cost.)k(Our)14 b(algorithm)f(assumes)h(existence)h(of)e(a)1431 621 y(~)1420 632 y Fp(O)q Fq(\()p Fp(n)1501 616 y Fm(2)1521 632 y Fq(\)-time)h(algorithm)g(with)0 689 y([)p Fp(\013;)8 b(\014)r Fq(])15 b(appro)o(ximation)h(guaran)o(tees)g(\(where,)g(as)g (usual,)h(the)f(notation)1276 677 y(~)1266 689 y Fp(O)q Fq(\(\))f(omits)h(factors)g(logarithmic)h(in)g Fp(n)0 745 y Fq(and)h(other)f(v)m(ariables\).)27 b(In)18 b(particular,)g(Jain) h(and)e(V)l(azirani)i([14)o(])e(giv)o(e)h(a)f(\(6)p Fp(;)8 b Fq(1\)-appro)o(ximation)15 b(algorithm,)0 801 y(while)i(Charik)m(ar)e (and)g(Guha)h([2)o(])f(giv)o(e)g(a)g(\(1)9 b(+)i Fp(\015)s(;)d Fq(1)g(+)i(2)p Fp(=\015)s Fq(\)-appro)o(ximation.)0 942 y(T)l(ree)15 b(\(MaxST\))e(and)i(Av)o(erage)f(Distance)h(\(AvgD\))e (\(see)i(the)f(de\014nitions)j(in)e(Section)h(2\).)j(The)14 b(exact)h(running)0 998 y(times)d(of)g(the)g(algorithms)g(are)g(giv)o (en)h(in)g(T)l(able)g(1.)18 b(The)13 b(crucial)g(prop)q(ert)o(y)f(of)g (our)f(algorithms)h(is)h(that)e(they)i(run)0 1054 y(in)h(time)g Fg(line)n(ar)266 1038 y Fm(1)299 1054 y Fq(in)g Fp(n)p Fq(.)19 b(As)14 b(the)g(size)g(of)f(the)h(metric)g(space)f(is)1066 1020 y Fk(\000)1085 1034 y Fl(n)1087 1070 y Fm(2)1107 1020 y Fk(\001)1126 1054 y Fq(,)g(their)h(complexit)o(y)h(is)f(in)g (fact)f Fg(subline)n(ar)g Fq(with)0 1111 y(resp)q(ect)j(to)f(the)g (input)i(size.)k(W)l(e)16 b(also)f(pro)o(vide)h(lo)o(w)o(er)g(b)q (ounds)g(for)f(sublinear)i(time)f(randomized)g(algorithms)0 1167 y(for)g(sev)o(eral)h(problems)g(\(see)g(page)g(9\).)23 b(Notice)18 b(that)e(for)g(MaxST,)f(MaxTSP)h(and)h(F)l(urthest)g(P)o (air)f(the)h(upp)q(er)0 1224 y(and)e(lo)o(w)o(er)g(b)q(ounds)h(matc)o (h.)71 1280 y(Our)f(tec)o(hniques)h(\(describ)q(ed)g(in)g(more)e (detail)i(at)e(the)h(end)g(of)f(this)h(section\))g(are)g(quite)g (general)h(and)e(their)0 1337 y(applicabili)q(t)o(y)k(do)q(es)e(not)g (seem)g(restricted)g(to)g(the)g(problems)g(considered)i(here.)23 b(Therefore,)15 b(w)o(e)h(exp)q(ect)h(that)0 1393 y(similar)d(results)f (can)g(b)q(e)h(obtain)f(for)f(other)h(problems)g(on)g(metric)g(spaces.) 20 b(W)l(e)13 b(also)g(note)f(that)g(our)h(algorithms)0 1450 y(are)e(easy)g(to)g(implemen)o(t)i(and)e(ha)o(v)o(e)g(small)h (constan)o(ts)f(in)h(the)f(running)i(time.)19 b(In)12 b(fact)e(our)h Fp(k)q Fq(-median)i(algorithm)0 1506 y(is)j(v)o(ery)f (similar)i(to)e(the)h(Scatter/Gather)e(clustering)j(pro)q(cedure)f(b)o (y)g(Cutting)f(et)h(al)f([4].)20 b(T)l(o)c(the)f(b)q(est)h(of)f(our)0 1563 y(kno)o(wledge)h(w)o(e)f(pro)o(vide)h(the)f(\014rst)g(formal)g (analysis)h(of)f(that)f(algorithm)h(\(or)g(in)h(fact)f(of)g(an)o(y)f (sampling-based)0 1619 y(clustering)i(algorithm\).)71 1675 y(In)f(the)f(remainder)h(of)f(this)h(section,)g(w)o(e)f(\014rst)g (motiv)m(ate)h(the)f(problems)h(considered)h(in)f(this)g(pap)q(er.)20 b(Then)0 1732 y(w)o(e)12 b(discuss)g(the)g(relation)h(of)e(our)h(w)o (ork)f(to)g(sev)o(eral)h(notions)g(dev)o(elop)q(ed)h(recen)o(tly)g(in)g (the)f(theory)f(of)g(algorithms,)0 1788 y(in)16 b(particular)g(to)e (prop)q(ert)o(y)h(testing)h(and)f(sp)q(ot)g(c)o(hec)o(king.)21 b(Finally)l(,)16 b(w)o(e)f(giv)o(e)h(an)f(o)o(v)o(erview)g(of)f(our)h (tec)o(hiques.)71 1845 y Ff(The)k(problems.)24 b Fq(The)17 b Fp(k)q Fq(-median)h(problem)g(is)f(of)g(in)o(terest)g(in)g(man)o(y)g (areas)f(suc)o(h)h(as)g(facilit)o(y)h(lo)q(cation,)0 1901 y(information)j(retriev)m(al)i(and)e(data)g(mining.)39 b(In)21 b(the)h(latter)f(t)o(w)o(o)e(areas)i(the)g(v)m(alue)i(of)d Fp(k)j Fq(is)e(usually)i(m)o(uc)o(h)0 1958 y(smaller)18 b(than)e Fp(n)h Fq(and)g(therefore)g(our)f(algorithm)h(o\013ers)f(a)g (signi\014can)o(t)i(impro)o(v)o(emen)o(t)e(in)i(running)g(time)f(o)o(v) o(er)0 2014 y(previous)e(\012\()p Fp(n)258 1998 y Fm(2)278 2014 y Fq(\)-time)g(algorithms.)k(The)c(next)f(t)o(w)o(o)g(problems)h (\(MaxTSP)e(and)i(MaxST\))f(are)g(maximization)0 2071 y(v)o(ersions)f(of)g(classical)h(optimization)h(problems;)f(unlik)o(e)g (the)f(minimization)j(problems)d(\(see)g(page)g(9\))g(they)g(can)0 2127 y(b)q(e)18 b(appro)o(ximated)f(up)h(to)f(a)g(small)h(constan)o(t)f (factor.)26 b(They)17 b(are)g(included)j(mainly)f(b)q(ecause)f(of)f (theoretical)0 2184 y(in)o(terest.)h(The)12 b(next)f(problem)g(\(MR)o (CST\))f(has)h(applications)h(to)e(net)o(w)o(ork)g(design)i([22)o(])f (and)g(molecular)g(biology)l(.)0 2240 y(The)17 b(latter)f(application)i (follo)o(ws)e(from)f(its)i(connection)g(to)f(Multiple)i(Sequence)g (Alignmen)o(t)f(\(MSA\),)f(where)0 2296 y(the)i(goal)g(is)h(to)f (\014nd)h(a)f(common)f(alignmen)o(t)i(of)f Fp(n)h Fq(genetic)g (sequences.)30 b(Sp)q(eci\014cally)l(,)22 b(Gus\014eld)d([9])e(sho)o(w) o(ed)0 2353 y(that)g(an)o(y)g(tree)g(within)i(cost)e(at)g(most)g Fp(c)g Fq(times)h(the)f(sum)h(of)f(all)h(distances)h(b)q(et)o(w)o(een)e (the)h(sequences)h(can)e(b)q(e)0 2409 y(used)g(to)e(\014nd)i(an)g (alignmen)o(t)f(within)i(factor)d Fp(c)h Fq(a)o(w)o(a)o(y)f(from)g (optimal.)24 b(The)16 b(alignmen)o(t)h(computation)f(step)g(is)0 2466 y(linear)d(in)g Fp(n)f Fq(and)g(th)o(us)g(our)g(tree)g (computation)f(pro)q(cedure)i(sp)q(eeds)g(up)g(Gus\014eld's)f (algorithm)g(as)g(w)o(ell.)20 b(Finally)l(,)0 2522 y(the)c(last)f (algorithm)h(\(for)e(the)i(Av)o(erage)f(Distance)h(problem\))g(is)g(a)f (useful)i(to)q(ol)f(for)f(gathering)g(statistics)h(o)o(v)o(er)p 0 2564 780 2 v 52 2591 a Fh(1)69 2607 y Fn(If)e(a)g(constan)o(t)h (probabilit)o(y)i(of)d(success)h(is)f(required;)i(otherwise)f(the)f (running)i(time)f(is)g(m)o(ultiplied)i(b)o(y)e(log)8 b(1)p Fe(=p)14 b Fn(where)g(1)c Fd(\000)f Fe(p)0 2653 y Fn(is)14 b(the)f(required)h(probabili)q(t)o(y)i(of)c(success)964 2825 y Fq(2)p eop %%Page: 3 3 3 2 bop 0 46 a Fq(the)15 b(metric)g(space.)20 b(F)l(or)14 b(example,)i(w)o(e)e(can)h(apply)h(it)f(to)f(estimate)h(the)g(gap)f(b)q (et)o(w)o(een)h(the)g(actual)g(solution)h(to)0 102 y(MSA)f(and)h(its)f (lo)o(w)o(er)g(b)q(ound.)71 159 y Ff(Prop)q(ert)o(y)d(testing)i(and)f (sp)q(ot)h(c)o(hec)o(king.)k Fq(In)13 b(the)e(last)h(t)o(w)o(o)e (decades)i(there)f(has)h(b)q(een)g(signi\014can)o(t)h(w)o(ork)0 215 y(on)h(estimating)g(the)g(complexit)o(y)g(of)g(c)o(hec)o(king)h Fg(gr)n(aph)f Fq(prop)q(erties.)20 b(In)14 b(particular,)h(Riv)o(est)f (and)g(V)l(uillemin)j([21)o(])0 271 y(sho)o(w)o(ed)11 b(that)g(the)g(problem)h(of)f(deciding)j(of)d Fg(any)g Fq(non-trivial)i(monotone)e(graph)g(prop)q(ert)o(y)g(requires)h(insp)q (ection)0 328 y(of)j(at)g(least)h(\012\()p Fp(n)293 311 y Fm(2)313 328 y Fq(\))f(edges;)h(the)g(same)f(b)q(ound)i(is)f (conjectured)g(to)f(hold)i(for)e(randomized)h(algorithms)g(as)f(w)o (ell.)0 384 y(V)l(ery)g(few)h(non-trivial)g(graph)f(prop)q(erties)h(ha) o(v)o(e)f(sub)q(quadratic)h(complexit)o(y)l(.)71 441 y(The)c(notion)h(of)g(appro)o(ximate)f(prop)q(ert)o(y)g(testing)h(\(in) o(tro)q(duced)h(b)o(y)e(Goldreic)o(h)i(et)e(al)h([7]\))f(is)h(a)f (relaxation)h(of)0 497 y(the)g(ab)q(o)o(v)o(e)f(de\014nition.)21 b(Sp)q(eci\014call)q(y)l(,)16 b(it)d(is)g(assumed)g(that)g(the)g(input) h(graph)e(either)i(satis\014es)f(a)g(prop)q(ert)o(y)f Fp(P)19 b Fq(or)0 554 y(is)c(within)g(distance)g(at)f(least)g Fp(\017n)566 537 y Fm(2)600 554 y Fq(from)g(an)o(y)g(graph)g (satisfying)g Fp(P)6 b Fq(;)15 b(the)f(distance)h(b)q(et)o(w)o(een)g(t) o(w)o(o)d(graphs)i(is)h(the)0 610 y(Hamming)h(distance)h(b)q(et)o(w)o (een)f(their)g(adjacency)g(matrices.)22 b(Goldreic)o(h)17 b(et)f(al)g([7)o(])f(sho)o(w)o(ed)h(man)o(y)f(in)o(teresting)0 667 y(results)g(on)g(complexit)o(y)h(of)e(testing)h(appro)o(ximate)f (prop)q(erties;)h(in)h(particular)g(they)e(obtained)i(p)q(oly)q(\(1)p Fp(=\017)p Fq(\))e(and)0 723 y(exp\(1)p Fp(=\017)p Fq(\))h(b)q(ounds)i (on)e(the)h(complexit)o(y)g(of)g(colorabilit)o(y)l(,)g(clique,)i(cut)d (and)h(bisection)h(problems.)22 b(Their)16 b(w)o(ork)0 780 y(w)o(as)g(later)i(extended)g(b)o(y)f(Ergun)g(et)g(al)h([6)o(],)f (who)g(in)o(tro)q(duced)i(the)e(notion)h(of)f Fg(sp)n(ot-che)n(cking)p Fq(.)25 b(They)17 b(applied)0 836 y(it)i(to)e(a)h(v)m(ariet)o(y)h(of)f (problems)h(on)f(graphs,)h(sets)f(and)g(algebra)h(obtaining)g (algorithms)f(with)h(running)h(times)0 892 y(v)m(arying)15 b(from)f Fp(O)q Fq(\(log)8 b Fp(n)p Fq(p)q(oly)q(\(1)p Fp(=\017)p Fq(\)\))13 b(to)h Fp(O)q Fq(\()741 860 y Fj(p)p 779 860 28 2 v 32 x Fp(n)p Fq(p)q(oly)q(\(1)p Fp(=\017)p Fq(\)\),)f(where)i Fp(n)g Fq(is)g(the)f(input/output)h(size)h(and)f Fp(\017n)g Fq(is)g(the)0 949 y(distance)h(from)e(the)i(correct)f (solution.)71 1005 y(The)h(main)g(di\013erence)i(b)q(et)o(w)o(een)e (appro)o(ximate)g(prop)q(ert)o(y)g(testing/sp)q(ot-c)o(hec)o(king)h (and)f(our)g(approac)o(h)f(is)0 1062 y(that)k(w)o(e)g(do)h(not)f(need)h (to)f(relax)h(the)f(original)i(problem)f(w.r.t)e(the)i(\\closeness")g (to)f(the)g(correct)h(solution.)0 1118 y(Rather)f(than)f(that,)h(w)o(e) f(relax)h(the)g(qualit)o(y)g(of)f(the)h(output,)g(whic)o(h)h(is)f(a)f (more)g(standard)h(w)o(a)o(y)e(of)h(de\014ning)0 1175 y(appro)o(ximate)j(v)o(ersions)h(of)f(problems.)698 1158 y Fm(2)758 1175 y Fq(On)h(the)g(other)f(hand,)j(our)d(tec)o(hniques)i (seem)f(to)f(b)q(e)h(limited)i(to)0 1231 y(problems)16 b(o)o(v)o(er)e(metric)i(spaces)f(only)l(.)71 1288 y Ff(Our)j(tec)o (hniques.)23 b Fq(All)18 b(of)d(our)h(algorithms)h(emplo)o(y)f(random)g (sampling.)24 b(There)17 b(are)f(t)o(w)o(o)f(basic)i(prop-)0 1344 y(erties)g(of)f(a)g(random)g(sample)h(of)f(a)g(metric)h(space)f(p) q(oin)o(ts)h(whic)o(h)h(w)o(e)e(use.)24 b(The)16 b(\014rst)g(prop)q (ert)o(y)g(is)h(that)f(large)0 1401 y(distances)h(\\cannot)e(hide")j (in)f(a)e(metric)i(space)f(\(more)g(sp)q(eci\014cally)l(,)j(if)d(there) g(is)h(an)o(y)f(pair)g(of)g(v)o(ertices)g(of)g(dis-)0 1457 y(tance)c(\001,)h(then)f(there)h(are)f(at)f(least)i Fp(n)f Fq(other)g(pairs)h(of)e(distance)i(at)f(least)g(\001)p Fp(=)p Fq(2)g(\(b)o(y)g(triangle)h(inequalit)o(y\).)20 b(Th)o(us)0 1513 y(w)o(e)e(can)h(sp)q(ot)f(one)h(suc)o(h)f(a)h(pair)f (b)o(y)h(random)f(sampling)h(or)f(insp)q(ection)j(of)d(a)g(neigh)o(b)q (orho)q(o)q(d)i(of)e(one)g(v)o(ertex)0 1570 y(\(this)c(for)g(example)g (giv)o(es)h(an)f(immediate)h(solution)g(to)e(the)h(F)l(urthest)g(P)o (air)g(problem\).)20 b(Another)14 b(prop)q(ert)o(y)f(w)o(e)0 1626 y(use)j(is)f(that)g(a)g(randomly)g(sampled)h(edge)g Fp(e)f Fq(from)g(a)g(set)g Fp(S)i Fq(has)e(exp)q(ected)i(length)f Fp(d)p Fq(\()p Fp(e)p Fq(\))e(equal)i(to)f(the)g(a)o(v)o(erage)0 1683 y(w)o(eigh)o(t)f(of)f(edges)i(in)g Fp(S)s Fq(.)k(This)14 b(can)g(b)q(e)h(used)g(for)e(\014nding)j(appro)o(ximation)e(of)f Fp(S)k Fq(or)c(its)i(cost,)e(pro)o(vided)i(that)e(w)o(e)0 1739 y(can)i(pro)o(v)o(e)g(additional)i(prop)q(erties)e(of)g(the)h(exp) q(ectation)f(or)g(v)m(ariance)h(of)f Fp(w)q Fq(\()p Fp(e)p Fq(\).)0 1883 y Fr(2)67 b(Preliminaries)0 1984 y Fq(Assume)16 b(w)o(e)g(are)g(giv)o(en)h(a)f(metric)g(space)g(\()p Fp(X)q(;)8 b(d)p Fq(\),)14 b(suc)o(h)j(that)e Fj(j)p Fp(X)t Fj(j)e Fq(=)h Fp(n)p Fq(.)23 b(The)17 b(problems)g(are)e(then)i (de\014ned)g(as)0 2040 y(follo)o(ws.)0 2147 y Ff(De\014nition)i(1)k(\() p Fp(k)q Ff(-median\):)f Fg(Find)16 b Fp(k)h Fq(medians)g Fp(c)925 2154 y Fm(1)952 2147 y Fp(:)8 b(:)g(:)e(c)1033 2154 y Fl(k)1066 2147 y Fj(2)13 b Fp(X)20 b Fg(which)d(minimize)e(the)i (value)f(of)810 2208 y Fk(X)804 2300 y Fl(p)p Fz(2)p Fl(X)899 2249 y Fq(min)884 2279 y Fl(i)p Fm(=1)p Fl(:::k)998 2249 y Fp(d)p Fq(\()p Fp(p;)8 b(c)1104 2256 y Fl(i)1116 2249 y Fq(\))p Fp(:)71 2399 y Fq(The)17 b(problem)g(is)g(MAX)g (SNP-hard.)25 b(Lin)18 b(and)f(Vitter)f([19)o(,)h(20)o(])g(ga)o(v)o(e)e (a)i(bicriterion)h([1)11 b(+)g Fp(\017;)d Fq(2\(1)i(+)i(1)p Fp(=\017)p Fq(\)]-)0 2455 y(appro)o(ximation)k(algorithm)h(for)f(an)o (y)g Fp(\017)f(>)g Fq(0,)h(i.e.)25 b(the)16 b(algorithm)h(outputs)f (2\(1)10 b(+)h(1)p Fp(=\017)p Fq(\))p Fp(k)17 b Fq(medians)h(with)e (cost)0 2512 y(at)f(most)h(\(1)10 b(+)h Fp(\017)p Fq(\))16 b(times)g(the)g(minim)o(um)i Fp(k)q Fq(-median)f(cost.)22 b(Their)17 b(algorithm)f(uses)g(linear)h(programming)f(and)0 2568 y(its)d(running)i(time)e(is)h(a)f(large)g(degree)g(p)q(olynomial)i (in)f Fp(n)p Fq(.)20 b(Charik)m(ar)13 b(et)g(al)g([3])g(ga)o(v)o(e)f(a) h([1)p Fp(;)8 b(O)q Fq(\(1\)]-appro)n(ximation)p 0 2610 780 2 v 52 2637 a Fh(2)69 2653 y Fn(In)13 b(some)h(cases)f(these)h(t)o (w)o(o)f(approac)o(hes)h(coincide;)h(for)e(example)i(it)f(w)o(as)f(sho) o(wn)g(in)h([7])f(that)g(b)o(y)h(using)g(their)g(tec)o(hniques)h(one)0 2699 y(can)e(obtain)i(a)e(\(1)c(+)f Fe(\017)p Fn(\)-appro)o(ximation)15 b(of)e(MAX-CUT)f(in)h(dense)h(graphs)g(in)g(time)f(linear)i(in)f(the)f (n)o(um)o(b)q(er)h(of)f(v)o(ertices.)964 2825 y Fq(3)p eop %%Page: 4 4 4 3 bop 0 46 a Fq(algorithm)21 b(for)g(this)h(problem,)h(also)e(via)g (linear)i(programming.)37 b(Of)22 b(particular)f(imp)q(ortance)h(to)f (our)g(pa-)0 102 y(p)q(er)c(are)g(t)o(w)o(o)e(recen)o(tly)i(dev)o(elop) q(ed)i(algorithms)d(with)974 91 y(~)963 102 y Fp(O)q Fq(\()p Fp(n)1044 86 y Fm(2)1064 102 y Fq(\)-time:)23 b(the)17 b([1)p Fp(;)8 b Fq(6]-appro)o(ximation)15 b(b)o(y)h(Jain)i (and)0 159 y(V)l(azirani)e([14],)e(and)h(the)h([1)9 b(+)h Fp(\015)s(;)e Fq(1)h(+)h(2)p Fp(=\015)s Fq(]-appro)o(ximation)j(b)o(y)j (Charik)m(ar)f(and)g(Guha)g([2].)71 215 y(W)l(e)g(also)g(men)o(tion)h (that)e(a)h(related)h Fp(k)q Fg(-c)n(enter)f Fq(problem)h(\(where)f (the)g(goal)g(is)h(to)f(minimize)i(the)f Fg(maximum)0 271 y Fq(cluster)g(radius\))f(can)h(b)q(e)f(solv)o(ed)h(in)g (\(sublinear\))877 260 y(~)866 271 y Fp(O)q Fq(\()p Fp(k)q(n)p Fq(\))f(time)h([11)o(,)f(10)o(].)0 378 y Ff(De\014nition)k(2)k(\(Maxim) o(um)18 b(Spanning)j(T)l(ree)d(-)i(MaxST\):)d Fg(Find)g(a)h(sp)n (anning)e(tr)n(e)n(e)h Fp(T)24 b Fg(of)18 b Fp(X)j Fg(such)c(that)0 434 y(the)g(sum)f(of)g(its)g(e)n(dge)g(lengths)f(is)h(maximize)n(d.)71 540 y Fq(This)f(problem)h(can)g(b)q(e)f(solv)o(ed)h(exactly)g(in)g Fp(O)q Fq(\()p Fp(n)924 524 y Fm(2)943 540 y Fq(\)-time)g(b)o(y)f (minim)o(um)h(spanning)g(tree)f(tec)o(hniques.)0 647 y Ff(De\014nition)k(3)k(\(Maxim)o(um)15 b(T)l(ra)o(v)o(eling)h (Salesman)h(Problem)e(-)i(MaxTSP\):)e Fg(Find)f(a)i(simple)e(cycle)h (of)0 703 y(length)h Fp(n)g Fg(such)h(that)f(the)h(sum)f(of)h(its)f(e)n (dge)g(lengths)f(is)h(maximize)n(d.)71 809 y Fq(The)e(problem)h(is)g (MAX)f(SNP-hard.)20 b(Kosara)s(ju)13 b(et)h(al)h([18)o(])e(ga)o(v)o(e)h (a)1262 792 y Fm(5)p 1262 799 18 2 v 1262 825 a(7)1284 809 y Fq(-appro)o(ximation)h(algorithm)f(for)g(this)0 866 y(problem.)0 972 y Ff(De\014nition)19 b(4)k(\(Minim)o(um)16 b(Routing)i(Cost)e(Spanning)i(T)l(ree)e(-)g(MR)o(CST\):)f Fg(Find)g(a)h(sp)n(anning)d(tr)n(e)n(e)i Fp(T)0 1029 y Fg(such)h(that)h(the)g(metric)f Fp(d)439 1036 y Fl(T)483 1029 y Fg(induc)n(e)n(d)g(by)g Fp(T)22 b Fg(minimizes)15 b(the)h(value)h(of)859 1090 y Fk(X)839 1182 y Fl(p;q)q Fz(2)p Fl(X)947 1131 y Fp(d)971 1138 y Fl(T)998 1131 y Fq(\()p Fp(p;)8 b(q)r Fq(\))p Fp(:)71 1285 y Fq(The)15 b(problem)h(is)g(NP-hard.)k(W)l(ong)15 b([23)o(])g(sho)o(w)o(ed)g(ho)o (w)g(to)f(construct)h(\(in)h Fp(O)q Fq(\()p Fp(n)1465 1268 y Fm(2)1485 1285 y Fq(\)-time\))f(a)g(tree)g(with)g(cost)0 1341 y(at)h(most)g(t)o(wice)h(the)f(sum)h(of)f(pairwise)i(distances)f (of)f(the)h Fg(original)f Fq(metric,)h(th)o(us)f(also)h(at)f(most)g(t)o (wice)h(of)f(the)0 1398 y(minim)o(um)e(R)o(CST)e(cost.)19 b(W)l(u)12 b(et)h(al)g([22)o(])f(ga)o(v)o(e)f(a)i(\(1)5 b(+)g Fp(\017)p Fq(\)-appro)o(ximation)12 b(algorithm)g(running)i(in)f (time)g Fp(n)1830 1381 y Fl(O)q Fm(\(1)p Fl(=\017)p Fm(\))1937 1398 y Fq(.)0 1504 y Ff(De\014nition)19 b(5)k(\(Av)o(erage)16 b(Distance)j(-)f(AvgD\):)d Fg(Compute)1181 1486 y Fm(1)p 1149 1493 82 2 v 1149 1532 a Fq(\()1167 1514 y Fo(j)p Fi(X)r Fo(j)1182 1542 y Fh(2)1213 1532 y Fq(\))1243 1472 y Fk(P)1287 1515 y Fl(p<q)q 1504="" 1619="" 1635="" 1778="" 1863="" 1880="" 1936="" 1961="" 1976="" 1993="" 2004="" 2049="" 2106="" fz(2)p="" fl(x)1414="" y="" fp(d)p="" fq(\()p="" fp(p;)8="" b(q)r="" fq(\))p="" fg(.)71="" fq(the)15="" b(problem)h(can)f(b)q(e)h(solv)o(ed)g(trivially)h(in)f="" fp(o)q="" fp(n)929="" fm(2)948="" fq(\)-time.)0="" fr(3)67="" b="" fc(1)p="" fr(-median)0="" fq(in)23="" b(this)g(section)h(w)o(e)e(presen)o(t)h(an)f="" fp(n="\016)756" fm(5)776="" fq(\)-time)g(\(1)15="" b(+)g="" fp(\016)r="" fq(\)-appro)o(ximation)23="" b(algorithm)f(for)g(the)h="" (1-median)0="" y(problem.)71="" y(f)l(or)14="" b(a)g(giv)o(en)i(p)q="" (oin)o(t)f="" fp(p)g="" fq(let)g="" fp(s)s="" fp(p)p="" fq(\))d(=")679" fk(p)723="" fl(q)q="" fl(x)804="" fp(p;)c(q)r="" fq(\).)18="" b(the)d(main)h(part)e(of)g(our)h="" (algorithm)g(is)g(a)g="" fq(\(1)p="" fp(="\016)1810" fm(5)1829="" fq(\)-time)0="" y(pro)q(cedure)j(whic)o(h)h(giv)o="" (en)f(an)o(y)f(t)o(w)o(o)f(p)q(oin)o(ts)i="" fp(p)f="" fq(and)g="" fp(q)j="" fq(p)q(erforms)d(an)g(appro)o(ximate)g(comparison)h(of)f="" fq(\))f(and)0="" fp(q)r="" fq(\).)25="" b(more)16="" b(sp)q(eci\014cally)l(,)k(if)e="" fq(\))d="">)h Fq(\(1)11 b(+)h Fp(\016)r Fq(\))p Fp(S)s Fq(\()p Fp(q)r Fq(\),)j(then)j(with)f (probabilit)o(y)i(2)p Fp(=)p Fq(3)d(\(sa)o(y\))g(the)h(algorithm)g (will)0 2162 y(return)g Fp(p)p Fq(;)g(if)g Fp(S)s Fq(\()p Fp(q)r Fq(\))d Fp(>)i Fq(\(1)10 b(+)i Fp(\016)r Fq(\))p Fp(S)s Fq(\()p Fp(p)p Fq(\))j(then)i(with)g(same)g(probabilit)o(y)h (the)f(algorithm)f(will)j(return)e Fp(q)r Fq(;)g(otherwise)0 2219 y(the)g(output)f(is)i(arbitrary)l(.)24 b(Using)17 b(this)g(probabilistic)i(comparison)e(as)f(a)g(subroutine,)i(w)o(e)f (can)f(appro)o(ximate)0 2275 y(the)f(smallest)h Fp(S)s Fq(\()p Fp(q)r Fq(\))e(using)i Fp(O)q Fq(\()p Fp(n)p Fq(\))f(comparisons.)71 2331 y(The)i(comparison)f(pro)q(cedure)i(is)f (as)g(follo)o(ws.)24 b(Assume)17 b(that)f Fp(\016)h(<)1259 2314 y Fm(1)p 1259 2321 18 2 v 1259 2347 a(2)1281 2331 y Fq(.)25 b(Let)17 b Fp(t)e Fq(=)h Fp(d)p Fq(\()p Fp(p;)8 b(q)r Fq(\),)15 b(let)i Fp(r)f Fq(=)f(4)p Fp(t=\016)e Fq(+)f Fp(t)0 2388 y Fq(and)k(let)g Fp(B)i Fq(b)q(e)e(the)f(set)h(of)f (p)q(oin)o(ts)h(within)g(distance)h Fp(r)f Fq(from)f Fp(p)p Fq(.)20 b(The)c(algorithm)f(starts)f(from)h(estimating)h(the)0 2444 y(v)m(alue)i(of)f Fp(\015)h Fq(=)271 2422 y Fz(j)p Fl(B)r Fz(j)p 271 2434 48 2 v 284 2460 a Fl(n)324 2444 y Fq(.)26 b(More)16 b(sp)q(eci\014cally)l(,)21 b(it)c(c)o(ho)q(oses)g (uniformly)h(at)f(random)f(a)h(set)g Fp(S)j Fq(of)c Fp(s)h Fq(=)f Fp(O)q Fq(\(1)p Fp(=\016)r Fq(\))g(p)q(oin)o(ts)0 2511 y(from)i Fp(X)k Fq(and)c(computes)h Fp(\015)495 2495 y Fz(0)524 2511 y Fq(=)583 2489 y Fz(j)p Fl(S)r Fz(\\)p Fl(B)r Fz(j)p 583 2501 95 2 v 609 2527 a(j)p Fl(S)r Fz(j)682 2511 y Fq(.)30 b(Then)20 b(it)e(c)o(hec)o(ks)h(if)g Fp(\015)1112 2495 y Fz(0)1141 2511 y Fp(>)g(\016)r(=)p Fq(5;)g(if)g(so,)g(it)g(concludes)h(that)e Fp(\015)i(>)f(\016)r(=)p Fq(6,)0 2574 y(otherwise,)c(it)g(concludes)i(that)d Fp(\015)h(<)e(\016) r(=)p Fq(4)h(\(the)h(constan)o(ts)f(are)h(c)o(hosen)g(mainly)i(for)d (clarit)o(y)i(of)e(exp)q(osition\).)21 b(It)0 2630 y(is)15 b(easy)g(to)f(see)h(that)f(with)h(large)g(constan)o(t)f(probabilit)o(y) i(the)f(conclusions)h(are)f(correct.)k(In)c(the)g(follo)o(wing,)g(w)o (e)0 2687 y(sho)o(w)j(that)f(in)i(b)q(oth)f(cases)g(w)o(e)g(can)h(quic) o(kly)g(appro)o(ximately)g(compare)e Fp(S)s Fq(\()p Fp(p)p Fq(\))g(and)i Fp(S)s Fq(\()p Fp(q)r Fq(\).)27 b(In)19 b(the)f(\014rst)g(case)964 2825 y(4)p eop %%Page: 5 5 5 4 bop 0 46 a Fq(\(if)16 b Fp(\015)g Fj(\025)e Fp(\016)r(=)p Fq(6\))h(then)h(w)o(e)g(can)g(easily)h(sample)g(p)q(oin)o(ts)f(from)f Fp(B)r Fq(.)23 b(Moreo)o(v)o(er,)14 b(the)i(distances)h Fp(d)p Fq(\()p Fp(u;)8 b(p)p Fq(\))14 b(and)i Fp(d)p Fq(\()p Fp(u;)8 b(q)r Fq(\))0 102 y(for)14 b Fp(u)f Fj(2)g Fp(B)18 b Fq(are)d(b)q(ounded)h(from)e(ab)q(o)o(v)o(e;)h(also)g(w)o(e)f (sho)o(w)h(that)f(the)h(larger)g(of)g Fp(S)s Fq(\()p Fp(p)p Fq(\))f(and)h Fp(S)s Fq(\()p Fp(q)r Fq(\))f(can)h(b)q(e)h(b)q (ounded)0 159 y(from)i(b)q(elo)o(w.)31 b(Therefore)18 b(w)o(e)g(can)h(estimate)g(the)f(sum)h(of)f(the)h(distances)g(within)h Fp(B)h Fq(b)o(y)e(random)f(sampling)0 215 y(\(the)e(distances)h (outside)g(of)e Fp(B)k Fq(are)d(again)g(similar)h(for)f Fp(p)g Fq(and)g Fp(q)r Fq(\).)23 b(In)16 b(the)g(second)h(case,)f(most) f(p)q(oin)o(ts)i Fp(u)d Fj(2)h Fp(X)0 271 y Fq(are)e(so)g(far)g(a)o(w)o (a)o(y)f(from)g(b)q(oth)i Fp(p)f Fq(and)g Fp(q)j Fq(that)c(the)i (di\013erence)g(b)q(et)o(w)o(een)g Fp(d)p Fq(\()p Fp(p;)8 b(u)p Fq(\))j(and)j Fp(d)p Fq(\()p Fp(q)r(;)8 b(u)p Fq(\))j(is)j (relativ)o(ely)h(small,)0 328 y(whic)o(h)h(implies)h(that)e Fp(S)s Fq(\()p Fp(p)p Fq(\))f(and)h Fp(S)s Fq(\()p Fp(q)r Fq(\))f(are)h(close)h(to)e(eac)o(h)i(other)e(and)i(an)o(y)f(c)o(hoice)h (is)f(correct.)71 384 y(Consider)j(\014rst)f(the)h(case)g(when)g Fp(\015)g(<)g(\016)r(=)p Fq(4.)26 b(In)18 b(this)h(case)e(w)o(e)h(sho)o (w)f(that)g(the)g(di\013erence)i(b)q(et)o(w)o(een)f Fp(S)s Fq(\()p Fp(p)p Fq(\))0 441 y(and)e Fp(S)s Fq(\()p Fp(q)r Fq(\))f(is)h(negligible)j(\(i.e.)j(smaller)17 b(than)e Fp(\016)e Fj(\001)d Fq(min)q(\()p Fp(S)s Fq(\()p Fp(p)p Fq(\))p Fp(;)e(S)s Fq(\()p Fp(q)r Fq(\))o(\)\),)k(so)k(an)o(y)f(c)o (hoice)i(made)f(b)o(y)g(the)g(algorithm)0 497 y(is)22 b(correct.)36 b(The)22 b(argumen)o(t)e(is)h(as)g(follo)o(ws.)37 b(F)l(or)21 b Fp(v)j Fj(2)e Fp(X)i Fq(de\014ne)e Fp(S)1257 504 y Fm(1)1277 497 y Fq(\()p Fp(v)r Fq(\))f(=)1416 465 y Fk(P)1460 509 y Fl(u)p Fz(2)p Fl(B)1542 497 y Fp(d)p Fq(\()p Fp(v)r(;)8 b(u)p Fq(\))19 b(and)i Fp(S)1814 504 y Fm(2)1833 497 y Fq(\()p Fp(v)r Fq(\))h(=)0 522 y Fk(P)44 565 y Fl(u)t(=)-22 b Fz(2)p Fl(B)126 554 y Fp(d)p Fq(\()p Fp(v)r(;)8 b(u)p Fq(\).)17 b(Observ)o(e)d(that)f Fp(S)s Fq(\()p Fp(p)p Fq(\))f(=)h Fp(S)735 561 y Fm(1)754 554 y Fq(\()p Fp(p)p Fq(\))7 b(+)g Fp(S)890 561 y Fm(2)910 554 y Fq(\()p Fp(p)p Fq(\))13 b(and)h Fp(S)s Fq(\()p Fp(q)r Fq(\))e(=)h Fp(S)1246 561 y Fm(1)1265 554 y Fq(\()p Fp(q)r Fq(\))7 b(+)g Fp(S)1400 561 y Fm(2)1420 554 y Fq(\()p Fp(q)r Fq(\).)19 b(Notice)14 b(that)f(due)i(to)e(the)0 610 y(fact)i(that)f(for)h(an)o(y)g Fp(u)d Fj(2)h Fp(X)19 b Fq(the)c(triangle)h(inequalit)o(y)g(implies)i Fj(j)p Fp(d)p Fq(\()p Fp(p;)8 b(u)p Fq(\))g Fj(\000)i Fp(d)p Fq(\()p Fp(q)r(;)e(u)p Fq(\))p Fj(j)i(\024)j Fp(d)p Fq(\()p Fp(p;)8 b(q)r Fq(\))j(=)i Fp(t)p Fq(,)i(w)o(e)g(ha)o(v)o(e)651 734 y(\001)e(=)g Fj(j)p Fp(S)s Fq(\()p Fp(p)p Fq(\))8 b Fj(\000)i Fp(S)s Fq(\()p Fp(q)r Fq(\))p Fj(j)h(\024)i Fp(n)e Fj(\001)f Fp(t)j Fj(\024)1210 703 y Fp(\016)p 1210 723 23 2 v 1210 765 a Fq(4)1237 734 y Fp(r)q(n:)0 856 y Fq(On)i(the)f(other)g(hand)g Fp(S)s Fq(\()p Fp(p)p Fq(\))e Fj(\025)h Fp(S)560 863 y Fm(2)579 856 y Fq(\()p Fp(p)p Fq(\))f Fj(\025)h Fq(\(1)7 b Fj(\000)i Fp(\015)s Fq(\))p Fp(n)p Fq(\()p Fp(r)e Fj(\000)i Fp(t)p Fq(\))j Fj(\025)h Fq(\(1)8 b Fj(\000)1144 838 y Fl(\016)p 1143 845 18 2 v 1143 871 a Fm(4)1166 856 y Fq(\))p Fp(nr)15 b Fq(and)f(the)g(same)g(b)q(ound)h(holds)g(for)f Fp(S)s Fq(\()p Fp(q)r Fq(\).)0 912 y(Th)o(us)h(one)g(can)h(v)o(erify)f(that)g (indeed)i(\001)12 b Fj(\024)h Fp(\016)d Fq(min\()p Fp(S)s Fq(\()p Fp(p)p Fq(\))p Fp(;)e(S)s Fq(\()p Fp(q)r Fq(\)\))o(.)71 969 y(Consider)20 b(no)o(w)f(the)g(case)h(when)g Fp(\015)h(>)g(\016)r (=)p Fq(6.)32 b(In)20 b(this)g(case)f(w)o(e)g(\014rst)g(c)o(ho)q(ose)h (a)f(random)g(sample)h Fp(R)f Fq(of)h Fp(l)0 1025 y Fq(p)q(oin)o(ts)15 b(from)e Fp(B)r Fq(;)i(notice)g(that)e(b)o(y)h(c)o(ho)q(osing)h Fp(O)q Fq(\()p Fp(l)q(=\016)r Fq(\))d(random)i(elemen)o(ts)h(of)f Fp(X)j Fq(and)d(rejecting)h(those)f(whic)o(h)h(do)0 1081 y(not)h(b)q(elong)g(to)g Fp(B)r Fq(,)g(w)o(e)g(can)g(obtain)g(suc)o(h)g (a)g(sample)h(in)f Fp(O)q Fq(\()p Fp(l)q(=\016)r Fq(\))f(time)h(with)g (constan)o(t)f(probabilit)o(y)l(.)24 b(Then)16 b(w)o(e)0 1138 y(compute)h Fp(S)217 1121 y Fz(0)228 1138 y Fq(\()p Fp(p)p Fq(\))c(=)350 1106 y Fk(P)394 1149 y Fl(u)p Fz(2)p Fl(R)475 1138 y Fp(d)p Fq(\()p Fp(p;)8 b(u)p Fq(\))14 b(and)j Fp(S)740 1121 y Fz(0)751 1138 y Fq(\()p Fp(q)r Fq(\))d(=)872 1106 y Fk(P)916 1149 y Fl(u)p Fz(2)p Fl(R)997 1138 y Fp(d)p Fq(\()p Fp(q)r(;)8 b(u)p Fq(\))14 b(and)j(c)o(ho)q(ose)f Fp(p)g Fq(if)h Fp(S)1488 1121 y Fz(0)1499 1138 y Fq(\()p Fp(p)p Fq(\))d Fp(>)h(S)1653 1121 y Fz(0)1664 1138 y Fq(\()p Fp(q)r Fq(\))h(or)f Fp(q)k Fq(in)e(the)0 1194 y(opp)q(osite)f(case.)71 1251 y(T)l(o)f(pro)o(v)o(e)g(correctness)h(of) g(the)g(ab)q(o)o(v)o(e)f(pro)q(cedure,)i(w)o(e)e(\014rst)h(observ)o(e)f (that)h(if)g(\(sa)o(y\))f Fp(S)s Fq(\()p Fp(p)p Fq(\))d Fp(>)i Fq(\(1)c(+)h Fp(\016)r Fq(\))p Fp(S)s Fq(\()p Fp(q)r Fq(\),)0 1307 y(then)16 b Fp(S)132 1314 y Fm(1)151 1307 y Fq(\()p Fp(p)p Fq(\))c Fp(>)h Fq(\(1)c(+)i Fp(\016)r Fq(\))p Fp(S)434 1314 y Fm(1)453 1307 y Fq(\()p Fp(q)r Fq(\),)j(as)h(otherwise)g(w)o(e)g(w)o(ould)h(ha)o(v)o(e)297 1409 y Fp(S)s Fq(\()p Fp(p)p Fq(\))c(=)h Fp(S)475 1416 y Fm(1)494 1409 y Fq(\()p Fp(p)p Fq(\))c(+)i Fp(S)636 1416 y Fm(2)656 1409 y Fq(\()p Fp(p)p Fq(\))g Fj(\024)i Fq(\(1)d(+)g Fp(\016)r Fq(\))p Fp(S)938 1416 y Fm(1)957 1409 y Fq(\()p Fp(q)r Fq(\))g(+)g(\(1)g(+)g Fp(\016)r(=)p Fq(4\))p Fp(S)1280 1416 y Fm(2)1299 1409 y Fq(\()p Fp(q)r Fq(\))i Fj(\024)h Fq(\(1)c(+)i Fp(\016)r Fq(\))p Fp(S)s Fq(\()p Fp(q)r Fq(\))p Fp(:)0 1512 y Fq(Th)o(us)i(if)g(w)o(e)g(sho)o(w) g(that)f Fp(S)455 1495 y Fz(0)466 1512 y Fq(\()p Fp(p)p Fq(\))g(estimates)759 1494 y Fl(l)p 740 1501 48 2 v 740 1528 a Fz(j)p Fl(B)r Fz(j)793 1512 y Fp(S)821 1519 y Fm(1)841 1512 y Fq(\()p Fp(p)p Fq(\))g(\(and)h Fp(S)1047 1495 y Fz(0)1058 1512 y Fq(\()p Fp(q)r Fq(\))f(estimates)1349 1494 y Fl(l)p 1331 1501 V 1331 1528 a Fz(j)p Fl(B)r Fz(j)1384 1512 y Fp(S)1412 1519 y Fm(1)1431 1512 y Fq(\()p Fp(q)r Fq(\)\))g(with)i(an)f(additiv)o(e)h(error)0 1568 y(at)h(most)749 1604 y Fp(\016)p 748 1624 23 2 v 748 1666 a Fq(3)805 1604 y Fp(l)p 781 1624 63 2 v 781 1666 a Fj(j)p Fp(B)r Fj(j)856 1634 y Fq(max)o(\()p Fp(S)986 1641 y Fm(1)1006 1634 y Fq(\()p Fp(p)p Fq(\))p Fp(;)8 b(S)1114 1641 y Fm(1)1132 1634 y Fq(\()p Fp(q)r Fq(\)\))0 1749 y(w)o(e)13 b(are)f(done.)20 b(Since)14 b(the)f(exp)q(ected)h(v)m(alue)g(of)e Fp(S)838 1733 y Fz(0)849 1749 y Fq(\()p Fp(p)p Fq(\))g(is)i(equal)f(to) 1158 1731 y Fl(l)p 1139 1738 48 2 v 1139 1765 a Fz(j)p Fl(B)r Fz(j)1192 1749 y Fp(S)1220 1756 y Fm(1)1240 1749 y Fq(\()p Fp(p)p Fq(\))f(and)h(a)f(similar)i(fact)f(holds)g(for)f Fp(q)r Fq(,)h(w)o(e)0 1813 y(just)i(need)h(to)f(b)q(ound)h(the)f(v)m (ariance)i(of)d Fp(S)731 1796 y Fz(0)743 1813 y Fq(\()p Fp(p)p Fq(\))g(and)h Fp(S)935 1796 y Fz(0)947 1813 y Fq(\()p Fp(q)r Fq(\))f(with)i(resp)q(ect)f(to)g(their)h(exp)q (ectations.)21 b(T)l(o)15 b(this)g(end)0 1869 y(w)o(e)i(observ)o(e)g (that)g(b)q(oth)g(v)m(ariances)h Fp(D)680 1852 y Fm(2)700 1869 y Fq([)p Fp(S)744 1852 y Fz(0)755 1869 y Fq(\()p Fp(p)p Fq(\)])e(and)h Fp(D)972 1852 y Fm(2)992 1869 y Fq([)p Fp(S)1036 1852 y Fz(0)1047 1869 y Fq(\()p Fp(q)r Fq(\)])f(are)h(b)q(ounded)h(b)o(y)g Fp(l)q(r)1502 1852 y Fm(2)1521 1869 y Fq(.)26 b(On)18 b(the)f(other)g(hand,)0 1925 y(w)o(e)e(kno)o(w)g(that)f(for)h(an)o(y)g(p)q(oin)o(t)g Fp(u)e Fj(2)g Fp(X)18 b Fq(w)o(e)d(ha)o(v)o(e)g Fp(d)p Fq(\()p Fp(p;)8 b(u)p Fq(\))g(+)j Fp(d)p Fq(\()p Fp(u;)d(q)r Fq(\))i Fj(\025)j Fp(d)p Fq(\()p Fp(p;)8 b(q)r Fq(\))j(=)i Fp(t)i Fq(and)h(th)o(us)539 2051 y(max\()p Fp(S)670 2058 y Fm(1)689 2051 y Fq(\()p Fp(p)p Fq(\))p Fp(;)8 b(S)797 2058 y Fm(1)815 2051 y Fq(\()p Fp(q)r Fq(\)\))j Fj(\025)955 2021 y Fp(S)983 2028 y Fm(1)1003 2021 y Fq(\()p Fp(p)p Fq(\))e(+)i Fp(S)1145 2028 y Fm(1)1164 2021 y Fq(\()p Fp(q)r Fq(\))p 955 2041 267 2 v 1077 2083 a(2)1239 2051 y Fj(\025)i(j)p Fp(B)r Fj(j)p Fp(t=)p Fq(2)0 2167 y(and)h(therefore)g (max)o(\()p Fp(E)s Fq([)p Fp(S)460 2151 y Fz(0)470 2167 y Fq(\()p Fp(p)p Fq(\)])p Fp(;)8 b(E)s Fq([)p Fp(S)643 2151 y Fz(0)652 2167 y Fq(\()p Fp(q)r Fq(\)]\))j Fj(\025)i Fp(l)q(t=)p Fq(2.)19 b(Recall)c(that)e(w)o(e)h(assume)g Fp(S)1391 2174 y Fm(1)1410 2167 y Fq(\()p Fp(p)p Fq(\))e Fp(>)h(S)1557 2174 y Fm(1)1577 2167 y Fq(\()p Fp(q)r Fq(\).)18 b(By)c(Cheb)o(yshev)0 2224 y(inequalit)o(y)607 2297 y(Pr[)p Fj(j)p Fp(S)713 2278 y Fz(0)723 2297 y Fq(\()p Fp(p)p Fq(\))c Fj(\000)g Fp(E)s Fq([)p Fp(S)918 2278 y Fz(0)928 2297 y Fq(\()p Fp(p)p Fq(\)])p Fj(j)h(\025)i Fp(a)d Fj(\001)1129 2256 y(p)p 1167 2256 15 2 v 41 x Fp(lr)q Fq(])i Fj(\024)1292 2266 y Fq(1)p 1281 2286 44 2 v 1281 2328 a Fp(a)1305 2315 y Fm(2)1330 2297 y Fp(:)0 2401 y Fq(If)j(w)o(e)g(c)o(ho)q(ose)g Fp(l)e(>)g(a)355 2385 y Fm(2)375 2401 y Fq(4\(4)p Fp(=\016)e Fq(+)f(1\))579 2385 y Fm(2)608 2401 y Fj(\001)g Fq(9)p Fp(=\016)699 2385 y Fm(2)733 2401 y Fq(then)837 2363 y Fj(p)p 875 2363 15 2 v 38 x Fp(l)894 2384 y Fl(\016)p 894 2391 18 2 v 894 2417 a Fm(3)924 2384 y Fl(t)p 922 2391 V 922 2417 a Fm(2)957 2401 y Fj(\025)j Fp(ar)j Fq(and)f(the)g(deviation)h(of) f Fp(S)1513 2385 y Fz(0)1524 2401 y Fq(\()p Fp(p)p Fq(\))g(from)f Fp(E)s Fq([)p Fp(S)1786 2385 y Fz(0)1796 2401 y Fq(\()p Fp(p)p Fq(\)])g(can)0 2458 y(b)q(e)i(b)q(ounded)g(b)o(y)576 2533 y Fp(a)10 b Fj(\001)633 2492 y(p)p 671 2492 15 2 v 41 x Fp(lr)k Fj(\024)773 2502 y Fp(\016)p 773 2523 23 2 v 773 2564 a Fq(3)809 2502 y Fp(t)p 805 2523 V 805 2564 a Fq(2)833 2533 y Fp(l)f Fj(\024)914 2502 y Fp(\016)p 913 2523 V 913 2564 a Fq(3)941 2533 y Fp(E)s Fq([)p Fp(S)1022 2514 y Fz(0)1032 2533 y Fq(\()p Fp(p)p Fq(\)])e(=)1169 2502 y Fp(\016)p 1168 2523 V 1168 2564 a Fq(3)1196 2533 y Fp(S)1224 2540 y Fm(1)1244 2533 y Fq(\()p Fp(p)p Fq(\))1331 2502 y Fp(l)p 1308 2523 63 2 v 1308 2564 a Fj(j)p Fp(B)r Fj(j)0 2642 y Fq(whic)o(h)17 b(w)o(as)e(to)h(b)q(e)h(sho)o(wn.)22 b(The)17 b(same)e(error)h(b)q(ound)h(can)f(b)q(e)h(obtained)g(for)e Fp(S)1396 2625 y Fz(0)1408 2642 y Fq(\()p Fp(q)r Fq(\))g(as)h(w)o(ell.) 24 b(This)16 b(completes)0 2698 y(the)f(pro)q(of)g(of)g(correctness)g (for)g(the)g(second)h(case)f(and)g(the)g(whole)h(comparison)f(pro)q (cedure.)964 2825 y(5)p eop %%Page: 6 6 6 5 bop 71 46 a Fq(Using)17 b(the)h(probabilistic)h(comparator)d(as)h (a)g(subroutine,)i(w)o(e)e(can)g(easily)h(get)f(an)h Fp(O)q Fq(\()p Fp(n)p Fq(p)q(oly\(log)8 b Fp(n;)g Fq(1)p Fp(=\016)r Fq(\)-)0 102 y(time)18 b(algorithm)g(for)f(\(1)11 b(+)h Fp(\016)r Fq(\)-appro)o(ximate)17 b(1-median)i(in)f(the)g(follo)o (wing)g(w)o(a)o(y)l(.)27 b(Construct)17 b(a)g(binary)h(tour-)0 159 y(namen)o(t)g(tree)h(o)o(v)o(er)f(the)h(p)q(oin)o(ts)g(in)h Fp(X)t Fq(,)e(where)h(eac)o(h)g(in)o(ternal)h(no)q(de)f(p)q(erforms)g (a)f(comparison)h(of)f(v)m(alues)i(of)0 215 y(the)c(function)g Fp(S)s Fq(\(\))e(of)h(its)h(c)o(hildren)i(and)d(selects)i(the)e (smaller)i(one.)k(Set)15 b(the)h(comparison)g(qualit)o(y)g(parameter)0 271 y Fp(\016)22 255 y Fz(0)53 271 y Fq(to)j Fp(\016)r(=)8 b Fq(log)f Fp(n)20 b Fq(and)g(p)q(erform)f(eac)o(h)g(comparison)h Fp(O)q Fq(\(log)8 b Fp(n)p Fq(\))19 b(times,)h(th)o(us)g(ac)o(hieving)g (a)f(high)i(probabilit)o(y)f(of)0 328 y(correctness)d(of)g(all)i (comparisons.)26 b(Since)19 b(the)e(smallest)h(elemen)o(t)g Fp(S)s Fq(\()p Fp(p)p Fq(\))f(is)g(compared)h(at)f(most)f(log)8 b Fp(n)18 b Fq(times,)0 384 y(the)d(v)m(alue)i(of)d(the)i(selected)g (elemen)o(t)g Fp(S)s Fq(\()p Fp(q)r Fq(\))e(is)i(b)q(ounded)g(b)o(y)f (\(1)10 b(+)g Fp(\016)1178 368 y Fz(0)1190 384 y Fq(\))1208 368 y Fm(log)5 b Fl(n)1295 384 y Fj(\024)13 b Fq(1)d(+)h Fp(O)q Fq(\()p Fp(\016)r Fq(\).)71 441 y(W)l(e)18 b(can)h(ac)o(hiev)o (e)g(a)f(b)q(etter)h(running)g(time)g(b)o(y)g(applying)h(the)e (randomized)i(tournamen)o(t)d(tec)o(hnique)j(b)o(y)0 497 y(Klein)o(b)q(erg)d([15)o(].)j(The)15 b(details)h(are)f(v)o(ery)g (similar,)h(th)o(us)f(w)o(e)g(omit)g(the)g(description)i(here.)0 641 y Fr(4)67 b Fb(k)r Fr(-median)0 742 y Fq(In)17 b(this)g(section)g (w)o(e)f(presen)o(t)g(an)g Fp(O)q Fq(\()p Fp(n)p Fq(\)-time)h(appro)o (ximation)f(algorithm)g(for)g(the)g Fp(k)q Fq(-median)i(problem.)24 b(Our)0 798 y(pro)q(cedure)19 b(uses)f(a)f(blac)o(k-b)q(o)o(x)h([)p Fp(\013;)8 b(\014)r Fq(]-appro)o(ximation)995 787 y(~)985 798 y Fp(O)q Fq(\()p Fp(n)1066 782 y Fm(2)1085 798 y Fq(\)-time)18 b(algorithm,)g(whic)o(h)h(w)o(e)e(refer)h(to)f(as)g(BB.)0 855 y(Let)e Fp(s)e Fq(=)g Fp(a)187 821 y Fj(p)p 225 821 152 2 v 34 x Fp(k)q(n)8 b Fq(log)g Fp(k)17 b Fq(for)d Fp(a)f(>)g Fq(1)i(determined)h(later.)k(The)c(algorithm)f(is)h(as)e (follo)o(ws.)p 0 929 1979 2 v 0 1676 2 747 v 70 1023 a(1.)22 b(Cho)q(ose)15 b(a)g(set)g Fp(S)i Fq(of)e Fp(s)h Fq(p)q(oin)o(ts)f(sampled)h(without)f(replacemen)o(t)h(from)f Fp(X)70 1117 y Fq(2.)22 b(Run)16 b(the)f(BB)h Fp(k)q Fq(-median)g(algorithm)f(on)g Fp(S)s Fq(,)g(let)g Fp(C)1014 1100 y Fz(0)1038 1117 y Fq(=)e Fp(c)1106 1100 y Fz(0)1106 1128 y Fm(1)1133 1117 y Fp(:)8 b(:)g(:)e(c)1214 1100 y Fz(0)1214 1130 y Fl(\014)r(k)1272 1117 y Fq(denote)15 b(the)g(output)70 1211 y(3.)22 b(Assign)15 b(eac)o(h)g(p)q(oin)o(t)g Fp(p)e Fj(2)g Fp(X)18 b Fq(to)c(a)g(p)q(oin)o(t)i(in)f Fp(C)927 1194 y Fz(0)954 1211 y Fq(within)h(smallest)f(distance)h(from) e Fp(p)p Fq(;)g(let)i Fp(d)p Fq(\()p Fp(p;)8 b(C)1791 1194 y Fz(0)1800 1211 y Fq(\))15 b(denote)128 1267 y(that)f(distance)70 1361 y(4.)22 b(Select)c(the)e(set)h Fp(M)22 b Fq(con)o(taining)17 b(the)g(p)q(oin)o(ts)g Fp(p)g Fq(with)g Fp(m)e Fq(=)h Fp(b)1195 1343 y Fl(k)q(n)p 1195 1350 41 2 v 1206 1377 a(s)1247 1361 y Fq(log)9 b Fp(k)18 b Fq(largest)e(v)m(alues)i(of)e Fp(d)p Fq(\()p Fp(p;)8 b(C)1816 1344 y Fz(0)1826 1361 y Fq(\),)16 b(for)h Fp(b)128 1417 y Fq(determined)f(later)70 1511 y(5.)22 b(Run)16 b(the)f(BB)h(algorithm)f(on)g Fp(M)5 b Fq(,)15 b(let)h Fp(C)834 1495 y Fz(00)870 1511 y Fq(denote)f(the)g (output)70 1605 y(6.)22 b(Output)15 b Fp(C)325 1589 y Fz(0)352 1605 y Fq(and)g Fp(C)476 1589 y Fz(00)p 1977 1676 2 747 v 0 1678 1979 2 v 71 1734 a Fq(In)j(the)f(follo)o(wing)h(w)o (e)f(will)i(use)f Fp(a)e Fq(=)g(\002\(1)p Fp(=\016)854 1698 y Fk(p)p 895 1698 134 2 v 895 1734 a Fq(log)9 b(1)p Fp(=\016)q Fq(\))17 b(and)g Fp(b)f Fq(=)h(\002\(1)p Fp(=\016)1363 1718 y Fm(2)1389 1734 y Fq(log)9 b(1)p Fp(=\016)r Fq(\).)25 b(It)17 b(is)h(easy)f(to)g(v)o(erify)0 1791 y(that)d(the)i(running)g (time)g(of)e(the)i(algorithm)f(is)843 1779 y(~)833 1791 y Fp(O)q Fq(\()p Fp(k)q(n=\016)984 1774 y Fm(2)1003 1791 y Fq(\).)k(It)d(remains)f(to)g(pro)o(v)o(e)f(its)i(correctness.)0 1897 y Ff(Theorem)h(1)23 b Fg(F)m(or)11 b(any)h(c)n(onstant)e Fp(\016)15 b(>)e Fq(0)e Fg(the)h(ab)n(ove)f(algorithm)i(c)n(omputes)e (a)h Fq([\(1+)p Fp(\016)r Fq(\)3\(2+)p Fp(\013)p Fq(\))p Fp(;)c Fq(2)p Fp(\014)r Fq(])p Fg(-appr)n(oximate)0 1953 y(solution)16 b(for)h(the)f Fp(k)q Fg(-me)n(dian)g(pr)n(oblem)h(with)f (pr)n(ob)n(ability)g Fq(\012\()p Fp(\016)r Fq(\))p Fg(.)71 2060 y Fq(By)g(running)i(the)f(ab)q(o)o(v)o(e)f(pro)q(cedure)h Fp(O)q Fq(\(1)p Fp(=\016)r Fq(\))e(times)i(and)g(taking)f(the)h (solution)g(with)g(the)g(smallest)g(cost,)0 2116 y(w)o(e)e(can)g (reduce)h(the)g(error)e(probabilit)o(y)j(to)d(an)o(y)h(constan)o(t.)71 2173 y Ff(Pro)q(of:)24 b Fq(The)18 b(2)p Fp(\014)h Fq(factor)d(is)i (clear,)g(th)o(us)g(w)o(e)f(fo)q(cus)h(on)f(pro)o(ving)h(the)f(\014rst) g(b)q(ound.)28 b(Let)18 b Fp(c)1673 2180 y Fm(1)1700 2173 y Fp(:)8 b(:)g(:)d(c)1780 2180 y Fl(k)1819 2173 y Fq(denote)0 2229 y(the)14 b(optimal)g(medians)g(and)g(let)g Fp(D)g Fq(denote)g(the)f(optimal)h(cost.)19 b(Let)14 b Fp(C)1230 2236 y Fl(i)1257 2229 y Fq(denote)g(the)f(set)g(of)h(p)q (oin)o(ts)f(in)i Fp(X)i Fq(closer)0 2285 y(to)h Fp(c)79 2292 y Fl(i)111 2285 y Fq(than)g(to)g(an)o(y)g(other)g Fp(c)510 2292 y Fl(j)547 2285 y Fq(\(for)f(simplicit)o(y)k(assume)d (there)h(are)f(no)g(ties\).)30 b(Also,)19 b(let)g Fp(C)1626 2269 y Fz(0)1623 2298 y Fl(i)1656 2285 y Fq(=)f Fp(S)d Fj(\\)d Fp(C)1827 2292 y Fl(i)1841 2285 y Fq(.)30 b(Let)0 2342 y Fp(t)13 b Fq(=)g Fp(b)102 2324 y Fl(n)p 102 2331 22 2 v 105 2358 a(s)135 2342 y Fq(log)c Fp(k)q Fq(.)20 b(Let)15 b Fp(L)e Fq(=)g Fj(f)p Fp(i)f Fq(:)g Fj(j)p Fp(C)555 2349 y Fl(i)568 2342 y Fj(j)g(\025)h Fp(t)p Fj(g)p Fq(,)i Fp(l)e Fq(=)783 2310 y Fk(P)827 2353 y Fl(i)p Fz(2)p Fl(L)896 2342 y Fj(j)p Fp(C)942 2349 y Fl(i)956 2342 y Fj(j)h Fq(and)i Fp(l)1087 2325 y Fz(0)1110 2342 y Fq(=)1158 2310 y Fk(P)1202 2353 y Fl(i)p Fz(2)p Fl(L)1271 2342 y Fj(j)p Fp(C)1320 2325 y Fz(0)1317 2354 y Fl(i)1331 2342 y Fj(j)p Fq(.)k(Clearly)c Fp(l)d Fj(\025)g Fp(n)d Fj(\000)h Fp(k)q(t)p Fq(.)0 2439 y Ff(Claim)18 b(1)445 2549 y Fq(Pr[)507 2508 y Fk(X)507 2600 y Fl(i)p Fz(2)p Fl(L)584 2508 y Fk(X)574 2603 y Fl(p)p Fz(2)p Fl(C)643 2591 y Fo(0)641 2615 y Fi(i)661 2549 y Fp(d)p Fq(\()p Fp(c)723 2556 y Fl(i)736 2549 y Fp(;)8 b(p)p Fq(\))k Fj(\025)866 2518 y Fp(s)p 863 2538 28 2 v 863 2580 a(n)895 2549 y Fq(\(1)d(+)i Fp(\017)p Fq(\))1035 2508 y Fk(X)1059 2600 y Fl(i)1112 2508 y Fk(X)1102 2600 y Fl(p)p Fz(2)p Fl(C)1169 2605 y Fi(i)1189 2549 y Fp(d)p Fq(\()p Fp(c)1251 2556 y Fl(i)1264 2549 y Fp(;)d(p)p Fq(\)])j Fj(\024)1440 2518 y Fq(1)p 1403 2538 97 2 v 1403 2580 a(1)f(+)h Fp(\017)964 2825 y Fq(6)p eop %%Page: 7 7 7 6 bop 71 46 a Ff(Pro)q(of:)23 b Fq(Consider)18 b(an)o(y)e(sampled)i (elemen)o(t)g Fp(p)p Fq(.)25 b(With)18 b(a)e(probabilit)o(y)j(of)1383 28 y Fl(l)p 1377 35 22 2 v 1377 61 a(n)1421 46 y Fq(this)e(elemen)o(t)h (b)q(elongs)g(to)e Fp(C)1936 53 y Fl(i)0 102 y Fq(for)f Fp(i)f Fj(2)h Fp(L)p Fq(.)22 b(Conditioned)17 b(on)f(this)h(ev)o(en)o (t,)f(the)g(exp)q(ected)h(v)m(alue)g(of)f Fp(d)p Fq(\()p Fp(p;)8 b(C)s Fq(\))14 b(is)1402 84 y Fm(1)p 1402 91 18 2 v 1405 118 a Fl(l)1433 70 y Fk(P)1476 114 y Fl(i)p Fz(2)p Fl(L)1546 70 y Fk(P)1589 114 y Fl(p)p Fz(2)p Fl(C)1656 119 y Fi(i)1679 102 y Fp(d)p Fq(\()p Fp(c)1741 109 y Fl(i)1754 102 y Fp(;)8 b(p)p Fq(\).)21 b(Th)o(us)0 165 y(the)13 b(exp)q(ected)i(v)m(alue)f(of)429 133 y Fk(P)473 177 y Fl(i)p Fz(2)p Fl(L)542 133 y Fk(P)586 177 y Fl(p)p Fz(2)p Fl(C)655 165 y Fo(0)653 188 y Fi(i)676 165 y Fp(d)p Fq(\()p Fp(c)738 172 y Fl(i)751 165 y Fp(;)8 b(p)p Fq(\))k(is)i Fp(s)895 147 y Fm(1)p 895 154 V 898 181 a Fl(l)928 147 y(l)p 923 154 22 2 v 923 181 a(n)957 133 y Fk(P)1000 177 y Fl(i)1022 133 y Fk(P)1066 177 y Fl(p)p Fz(2)p Fl(C)1133 182 y Fi(i)1155 165 y Fp(d)p Fq(\()p Fp(c)1217 172 y Fl(i)1230 165 y Fp(;)8 b(p)p Fq(\).)18 b(The)c(Claim)g(follo)o(ws)f (from)g(Mark)o(o)o(v)0 222 y(inequalit)o(y)l(.)1713 b Fa(2)0 340 y Ff(Claim)18 b(2)23 b Fg(F)m(or)16 b(any)g Fp(\015)f(>)e Fq(0)j Fg(we)g(have)476 464 y Fq(Pr)o([)p Fg(for)h(every)f Fp(i)c Fj(2)h Fp(L;)858 433 y Fj(j)p Fp(C)904 440 y Fl(i)917 433 y Fj(j)p 857 453 73 2 v 857 495 a(j)p Fp(C)906 479 y Fz(0)903 508 y Fl(i)917 495 y Fj(j)947 464 y(\024)1000 433 y Fp(n)p 1000 453 28 2 v 1003 495 a(s)1033 464 y Fq(\(1)c(+)i Fp(\015)s Fq(\)])g Fj(\025)i Fq(1)c Fj(\000)i Fq(2)p Fp(k)q(e)1407 422 y Fo(\000)p Fi(st)p 1398 429 70 2 v 1398 454 a Fh(3)p Fi(n\015)1450 447 y Fh(2)71 593 y Ff(Pro)q(of:)19 b Fq(F)l(ollo)o(ws)c(from)g (Cherno\013)g(b)q(ound.)1092 b Fa(2)71 662 y Fq(Assume)15 b(that)g(b)q(oth)g(assertions)g(of)g(the)g(ab)q(o)o(v)o(e)g(Claims)h (hold)g(\(whic)o(h)g(is)g(true)f(with)h(probabilit)o(y)g(\002\()p Fp(\017)p Fq(\))g(for)0 719 y(a)i(prop)q(er)g(c)o(hoice)h(of)f Fp(a)g Fq(and)g Fp(b)p Fq(\).)28 b(W)l(e)19 b(sho)o(w)e(that)h(the)g (cen)o(ters)g Fp(C)1166 702 y Fz(0)1195 719 y Fq(pro)o(vide)h(a)f(go)q (o)q(d)g(solution)h(for)e(all)j(p)q(oin)o(ts)0 775 y(from)15 b Fj([)138 782 y Fl(i)p Fz(2)p Fl(L)200 775 y Fp(C)233 782 y Fl(i)246 775 y Fq(.)22 b(Fix)16 b(an)o(y)f(suc)o(h)h Fp(C)585 782 y Fl(i)614 775 y Fq(and)g(consider)h(an)o(y)e(function)h Fp(q)1165 782 y Fl(i)1193 775 y Fq(:)d Fp(C)1252 782 y Fl(i)1279 775 y Fj(!)h Fp(C)1374 759 y Fz(0)1371 787 y Fl(i)1401 775 y Fq(suc)o(h)i(that)f(an)o(y)g(elemen)o(t)i(from)0 839 y Fp(C)36 822 y Fz(0)33 851 y Fl(i)61 839 y Fq(has)d(at)f(most)311 816 y Fz(j)p Fl(C)346 821 y Fi(i)359 816 y Fz(j)p 311 828 59 2 v 311 855 a(j)p Fl(C)348 844 y Fo(0)346 867 y Fi(i)359 855 y Fz(j)388 839 y Fq(elemen)o(ts)h(assigned)h(to)e(it.)20 b(F)l(or)13 b(an)o(y)h Fp(q)g Fj(2)f Fp(C)1146 822 y Fz(0)1143 851 y Fl(i)1172 839 y Fq(let)h Fp(c)1256 822 y Fz(0)1267 839 y Fq(\()p Fp(q)r Fq(\))g(denote)g(the)g(median)h Fp(c)1739 822 y Fz(0)1739 851 y Fl(i)1766 839 y Fq(closest)g(to)0 902 y Fp(q)r Fq(.)20 b(By)15 b(triangle)h(inequalit)o(y)472 1005 y Fp(d)p Fq(\()p Fp(p;)8 b(C)594 986 y Fz(0)604 1005 y Fq(\))k Fj(\024)h Fp(d)p Fq(\()p Fp(p;)8 b(c)788 1012 y Fl(i)800 1005 y Fq(\))i(+)g Fp(d)p Fq(\()p Fp(c)935 1012 y Fl(i)948 1005 y Fp(;)e(q)989 1012 y Fl(i)1003 1005 y Fq(\()p Fp(p)p Fq(\)\))h(+)h Fp(d)p Fq(\()p Fp(q)1196 1012 y Fl(i)1210 1005 y Fq(\()p Fp(p)p Fq(\))p Fp(;)e(c)1310 986 y Fz(0)1320 1005 y Fq(\()p Fp(q)1358 1012 y Fl(i)1372 1005 y Fq(\()p Fp(p)p Fq(\)\)\))p Fp(:)71 1107 y Fq(Th)o(us)396 1168 y Fk(X)396 1260 y Fl(i)p Fz(2)p Fl(L)473 1168 y Fk(X)464 1260 y Fl(p)p Fz(2)p Fl(C)531 1265 y Fi(i)551 1209 y Fp(d)p Fq(\()p Fp(p;)g(C)673 1190 y Fz(0)682 1209 y Fq(\))42 b Fj(\024)819 1168 y Fk(X)819 1260 y Fl(i)p Fz(2)p Fl(L)878 1209 y Fq([)901 1168 y Fk(X)891 1260 y Fl(p)p Fz(2)p Fl(C)958 1265 y Fi(i)978 1209 y Fp(d)p Fq(\()p Fp(p;)8 b(c)1084 1216 y Fl(i)1096 1209 y Fq(\))819 1352 y(+)859 1322 y Fj(j)p Fp(C)905 1329 y Fl(i)918 1322 y Fj(j)p 859 1342 73 2 v 859 1383 a(j)p Fp(C)908 1368 y Fz(0)905 1396 y Fl(i)919 1383 y Fj(j)954 1312 y Fk(X)944 1406 y Fl(q)q Fz(2)p Fl(C)1012 1395 y Fo(0)1010 1418 y Fi(i)1023 1352 y Fq(\()p Fp(d)p Fq(\()p Fp(c)1103 1359 y Fl(i)1116 1352 y Fp(;)g(q)r Fq(\))h(+)h Fp(d)p Fq(\()p Fp(q)r(;)e(c)1336 1334 y Fz(0)1346 1352 y Fq(\()p Fp(q)r Fq(\)\)\)])742 1489 y Fj(\024)42 b Fp(D)11 b Fq(+)918 1458 y Fp(n)p 918 1479 28 2 v 921 1520 a(s)950 1489 y Fq(\(1)f(+)g Fp(\015)s Fq(\)\(1)e(+)j(2)p Fp(\013)p Fq(\))1264 1449 y Fk(X)1263 1541 y Fl(i)p Fz(2)p Fl(L)1341 1449 y Fk(X)1331 1543 y Fl(p)p Fz(2)p Fl(C)1400 1532 y Fo(0)1398 1555 y Fi(i)1418 1489 y Fp(d)p Fq(\()p Fp(c)1480 1496 y Fl(i)1493 1489 y Fp(;)d(p)p Fq(\))742 1626 y Fj(\024)42 b Fp(D)11 b Fq(+)918 1595 y Fp(n)p 918 1615 V 921 1657 a(s)950 1626 y Fq(\(1)f(+)g Fp(\015)s Fq(\)\(1)e(+)j(2)p Fp(\013)p Fq(\)\(1)e(+)h Fp(\017)p Fq(\))1396 1595 y Fp(s)p 1392 1615 V 1392 1657 a(n)1425 1626 y(D)742 1708 y Fq(=)42 b(\(1)9 b(+)h Fp(\015)s Fq(\)\(1)f(+)h Fp(\017)p Fq(\)\(2)g(+)g(2)p Fp(\013)p Fq(\))p Fp(D)742 1777 y Fq(=)42 b(\(1)9 b(+)h Fp(\016)r Fq(\)\(2)g(+)g(2)p Fp(\013)p Fq(\))p Fp(D)71 1879 y Fq(As)i Fp(l)h Fq(=)g Fj(j)5 b([)258 1886 y Fl(i)p Fz(2)p Fl(L)324 1879 y Fp(C)357 1886 y Fl(i)371 1879 y Fj(j)12 b(\025)h Fp(n)5 b Fj(\000)g Fp(k)q(t)p Fq(,)13 b(w)o(e)f(kno)o(w)g(that)g(the)g(cost)g(of)g(the)h(p)q(oin)o (ts)g(in)g Fp(X)8 b Fj(\000)d Fp(M)18 b Fq(with)12 b(resp)q(ect)h(to)f (medians)0 1935 y Fp(C)36 1919 y Fz(0)63 1935 y Fq(do)q(es)17 b(not)e(exceed)i(\(1)10 b(+)h Fp(\016)r Fq(\)\(2)f(+)h(2)p Fp(\013)p Fq(\))k(as)h(w)o(ell.)23 b(Th)o(us)16 b(it)g(is)g(su\016cien) o(t)h(to)e(b)q(ound)i(the)f(cost)g(of)f(clustering)i(of)0 1992 y Fp(M)5 b Fq(.)27 b(T)l(o)18 b(this)g(end)g(notice,)h(that)e (there)h(exists)g(a)f(clustering)i(of)e Fp(M)23 b Fq(with)18 b(a)f(cost)h(at)f(most)g(2)p Fp(D)h Fq(\(just)f(replace)0 2048 y(eac)o(h)c Fp(c)120 2055 y Fl(i)147 2048 y Fq(b)o(y)g(its)g (closest)h(neigh)o(b)q(or)g(in)f Fp(M)5 b Fq(\).)19 b(Th)o(us)13 b(the)h(algorithm)f(will)h(\014nd)g(a)f(clustering)h(of)f Fp(M)18 b Fq(with)c(cost)e(2)p Fp(\013D)0 2105 y Fq(and)j(the)h(total)e (cost)h(do)q(es)g(not)g(exceed)h(\(1)10 b(+)g Fp(\016)r Fq(\)\(2)g(+)g(4)p Fp(\013)p Fq(\))p Fp(D)q Fq(.)865 b Fa(2)0 2260 y Fr(5)67 b(Maxim)n(um)24 b(Spanning)g(T)-6 b(ree)0 2362 y Fq(In)18 b(this)f(section)h(w)o(e)e(presen)o(t)h(t)o(w)o (o)f(appro)o(ximation)h(algorithms)g(for)f(MaxST,)g(b)q(oth)h(running)i (in)e Fp(O)q Fq(\()p Fp(n)p Fq(\))g(time.)0 2418 y(The)d(\014rst)f(one) h(outputs)g(a)f(tree)h(of)f(cost)g(at)h(least)865 2400 y Fm(1)p 865 2407 18 2 v 865 2434 a(4)901 2418 y Fq(times)g(the)g (optimal,)g(while)h(the)f(second)g(one)g(impro)o(v)o(es)g(the)0 2475 y(factor)g(to)191 2457 y Fm(1)p 191 2464 V 191 2490 a(2)213 2475 y Fq(.)71 2531 y(Let)i Fp(T)21 b Fq(denote)c(the)f(tree)f (with)i(maxim)o(um)e(cost)h Fp(C)s Fq(\()p Fp(T)6 b Fq(\))15 b(and)h(let)g(\001)g(b)q(e)g(the)g(diameter)h(of)e(the)h(graph.)22 b(The)0 2588 y(\014rst)15 b(algorithm)g(follo)o(ws)g(from)g(the)g (follo)o(wing)h(Lemma.)0 2694 y Ff(Lemma)h(1)23 b Fg(A)16 b(tr)n(e)n(e)g Fp(T)22 b Fg(of)17 b(c)n(ost)e(at)i(le)n(ast)729 2676 y Fl(n)p 729 2683 22 2 v 731 2710 a Fm(4)756 2694 y Fq(\001)f Fg(c)n(an)f(b)n(e)h(found)h(in)f Fp(O)q Fq(\()p Fp(n)p Fq(\))f Fg(time.)964 2825 y Fq(7)p eop %%Page: 8 8 8 7 bop 71 46 a Ff(Pro)q(of:)27 b Fq(Let)19 b Fp(a;)8 b(b)17 b Fj(2)i Fp(X)j Fq(b)q(e)e(p)q(oin)o(ts)f(suc)o(h)h(that)e Fp(d)p Fq(\()p Fp(a;)8 b(b)p Fq(\))16 b(=)j(\001.)31 b(Consider)20 b(arbitrary)e(p)q(oin)o(t)h Fp(q)r Fq(.)31 b(As)19 b(\001)g(=)0 102 y Fp(d)p Fq(\()p Fp(a;)8 b(b)p Fq(\))13 b Fj(\024)j Fp(d)p Fq(\()p Fp(a;)8 b(q)r Fq(\))i(+)h Fp(d)p Fq(\()p Fp(q)r(;)d(b)p Fq(\),)15 b(w)o(e)i(can)g(\014nd)h(a)e(v) o(ertex)h Fp(u)g Fq(suc)o(h)g(that)f Fp(d)p Fq(\()p Fp(q)r(;)8 b(u)p Fq(\))14 b Fj(\025)1395 84 y Fm(\001)p 1395 91 30 2 v 1401 118 a(2)1429 102 y Fq(.)26 b(Consider)17 b(no)o(w)g(t)o(w)o(o)e(stars:)0 159 y Fp(S)28 166 y Fl(q)62 159 y Fq(cen)o(tered)h(at)e Fp(q)j Fq(and)f Fp(S)452 166 y Fl(u)489 159 y Fq(cen)o(tered)g(at)f Fp(u)p Fq(.)k(W)l(e)d(can)f (lo)o(w)o(er)g(b)q(ound)h(the)f(sum)g(of)g(their)h(costs)f(b)o(y)592 223 y Fk(X)613 310 y Fl(p)659 264 y Fp(d)p Fq(\()p Fp(q)r(;)8 b(p)p Fq(\))h(+)h Fp(d)p Fq(\()p Fp(u;)e(p)p Fq(\))j Fj(\025)1028 223 y Fk(X)1049 310 y Fl(p)1095 264 y Fp(d)p Fq(\()p Fp(q)r(;)d(u)p Fq(\))j Fj(\025)i Fp(n)1315 233 y Fq(\001)p 1315 253 38 2 v 1323 295 a(2)0 391 y(Th)o(us)i(one)g(of)g Fp(S)278 398 y Fl(q)312 391 y Fq(and)h Fp(S)429 398 y Fl(u)466 391 y Fq(has)f(cost)g(at)g(least)808 374 y Fm(\001)p 808 381 30 2 v 814 407 a(4)842 391 y Fp(n)p Fq(.)1034 b Fa(2)71 457 y Fq(The)14 b(second)h(algorithm)f(uses)h(similar)g (idea,)g(but)g(the)f(pair)h(\()p Fp(q)r(;)8 b(u)p Fq(\))13 b(is)h(found)h(b)o(y)f(random)g(sampling)i(rather)0 513 y(than)h(using)g(the)g(ab)q(o)o(v)o(e)f(algorithm.)25 b(Sp)q(eci\014cally)m(,)19 b(w)o(e)e(pro)o(v)o(e)f(that)g(the)h (longest)g(among)f(the)h Fp(O)q Fq(\()p Fp(n)p Fq(\))f(sampled)0 576 y(edges)f(has)h(length)f(close)h(to)511 554 y Fl(C)r Fm(\()p Fl(T)5 b Fm(\))p 511 565 81 2 v 518 592 a Fl(n)p Fz(\000)p Fm(1)596 576 y Fq(.)20 b(The)15 b(b)q(ound)i(then)e(follo)o (ws)g(from)g(the)g(ab)q(o)o(v)o(e)g(argumen)o(t.)71 632 y(In)c(order)g(to)g(analyze)h(the)f(sampling)h(algorithm,)g(w)o(e)f (need)h(the)f(follo)o(wing)h(Lemma)g(\(whic)o(h)f(can)h(b)q(e)g(though) o(t)0 689 y(of)j(as)g(a)f(rev)o(erse)h(v)o(ersion)h(of)f(Mark)o(o)o(v)e (inequalit)o(y\).)0 775 y Ff(Lemma)k(2)23 b Fg(L)n(et)c Fp(X)24 b Fg(b)n(e)19 b(a)h(r)n(andom)g(variable)g(with)h(values)e(fr)n (om)h(the)h(set)e Fq([0)p Fp(;)8 b(B)r Fq(])19 b Fg(such)h(that)h Fp(E)s Fq([)p Fp(X)t Fq(])c Fj(\025)1840 757 y Fl(B)p 1840 764 29 2 v 1845 791 a(a)1894 775 y Fg(for)0 832 y(some)f Fp(a)d(>)g Fq(1)p Fg(.)20 b(Then)c(for)g(any)h Fp(\013)12 b(>)h Fq(0)708 921 y(Pr[)p Fp(X)i Fj(\025)e Fq(\(1)d Fj(\000)g Fp(\013)p Fq(\))p Fp(E)s Fq([)p Fp(X)t Fq(]])g Fj(\025)1195 890 y Fp(\013)p 1195 910 30 2 v 1198 952 a(a)1229 921 y(:)71 1018 y Ff(Pro)q(of:)19 b Fq(Similar)e(to)d(the)i(pro)q(of)f(of)f(Mark)o(o)o(v)g(inequalit)o(y)l (.)854 b Fa(2)71 1083 y Fq(W)l(e)19 b(can)h(no)o(w)f(pro)q(ceed)h(with) g(the)f(pro)q(of)g(of)g(correctness)h(of)f(the)g(sampling)i(pro)q (cedure.)33 b(Let)20 b Fp(e)1802 1090 y Fm(1)1829 1083 y Fp(:)8 b(:)g(:)e(e)1911 1090 y Fl(cn)0 1140 y Fq(denote)19 b Fp(cn)g Fq(edges)h(sampled)f(at)g(random;)h(let)f Fp(X)k Fq(=)c(max)1036 1147 y Fl(i)1057 1140 y Fp(d)p Fq(\()p Fp(e)1120 1147 y Fl(i)1134 1140 y Fq(\).)31 b(As)19 b(for)f(an)o(y)h Fp(\017)g(>)h Fq(0)e(and)i Fp(c)e Fq(=)i Fp(O)q Fq(\(log)7 b(1)p Fp(=\017)p Fq(\))0 1202 y(w)o(e)16 b(ha)o(v)o(e)g(the)g (probabilit)o(y)h(of)f(1)11 b Fj(\000)g Fp(\017)17 b Fq(of)e(hitting)i(a)f(\(random\))f(edge)i(from)e Fp(T)6 b Fq(,)16 b(w)o(e)g(ha)o(v)o(e)g Fp(E)s Fq([)p Fp(X)t Fq(])c Fj(\025)j Fq(\(1)10 b Fj(\000)h Fp(\017)p Fq(\))1852 1180 y Fl(C)r Fm(\()p Fl(T)5 b Fm(\))p 1852 1192 81 2 v 1859 1218 a Fl(n)p Fz(\000)p Fm(1)1937 1202 y Fq(.)0 1273 y(Therefore)13 b(\(b)o(y)g(Lemma)h(2\))f(w)o(e)g(conclude)i(that)e (with)g(a)h(probabilit)o(y)g(of)f(\012\()p Fp(\013)p Fq(\))g(w)o(e)g(ha)o(v)o(e)g Fp(X)j Fj(\025)d Fq(\(1)7 b Fj(\000)g Fp(\013)g Fj(\000)g Fp(\017)p Fq(\))1853 1250 y Fl(C)r Fm(\()p Fl(T)e Fm(\))p 1853 1262 V 1859 1288 a Fl(n)p Fz(\000)p Fm(1)1937 1273 y Fq(.)0 1329 y(Th)o(us)15 b(w)o(e)g(ha)o(v)o(e)g(pro)o(v)o(en)g(the)g(follo)o(wing)h (theorem.)0 1415 y Ff(Theorem)h(2)23 b Fg(F)m(or)11 b(any)h Fp(\016)i(>)f Fq(0)e Fg(ther)n(e)h(is)f(a)743 1397 y Fm(1)p Fz(\000)p Fl(\016)p 743 1404 62 2 v 765 1431 a Fm(2)810 1415 y Fg(-appr)n(oximation)i(algorithm)f(for)g(MaxST)f (running)f(in)i Fp(O)q Fq(\()p Fp(n)1847 1393 y Fm(log)5 b(1)p Fl(=\016)p 1847 1405 104 2 v 1890 1431 a(\016)1955 1415 y Fq(\))0 1472 y Fg(time.)0 1612 y Fr(6)67 b(Maxim)n(um)24 b(TSP)0 1713 y Fq(Let)17 b Fp(T)24 b Fq(denote)17 b(the)g(tour)g(with)h (maxim)o(um)f(cost)f Fp(C)s Fq(\()p Fp(T)6 b Fq(\))17 b(and)g(let)h Fp(T)1191 1697 y Fz(0)1219 1713 y Fq(b)q(e)g(tour)f(c)o (hosen)h(uniformly)g(at)e(random)0 1770 y(from)e(the)i(space)f(of)g (all)h(\()p Fp(n)10 b Fj(\000)h Fq(1\)!)j(tours.)0 1862 y Ff(Lemma)j(3)23 b Fp(E)s Fq([)p Fp(C)s Fq(\()p Fp(T)371 1846 y Fz(0)381 1862 y Fq(\)])12 b Fj(\025)477 1840 y Fl(C)r Fm(\()p Fl(T)5 b Fm(\))p 477 1852 81 2 v 508 1878 a(2)562 1862 y Fp(:)71 1959 y Ff(Pro)q(of:)17 b Fq(W)l(e)12 b(can)g(write)g Fp(E)s Fq([)p Fp(C)s Fq(\()p Fp(T)635 1943 y Fz(0)645 1959 y Fq(\)])f(as)739 1927 y Fk(P)783 1971 y Fl(p)810 1927 y Fk(P)854 1971 y Fl(q)q Fz(6)p Fm(=)p Fl(p)931 1937 y(d)p Fm(\()p Fl(p;q)q Fm(\))p 931 1949 91 2 v 943 1975 a Fl(n)p Fz(\000)p Fm(1)1026 1959 y Fq(.)18 b(Fix)12 b Fp(p)g Fq(and)g(let)g Fp(T)6 b Fq(\()p Fp(p)p Fq(\))11 b(denote)h(the)f(successor)h(of)g Fp(p)f Fq(in)0 2016 y(the)j(tour)g Fp(T)6 b Fq(.)20 b(By)14 b(triangle)h(inequalit)o(y)h(w)o(e)e(kno)o(w)g(that)f(for)h(an)o(y)g Fp(q)i Fq(w)o(e)e(ha)o(v)o(e)g Fp(d)p Fq(\()p Fp(p;)8 b(T)e Fq(\()p Fp(p)p Fq(\)\))k Fj(\025)j Fp(d)p Fq(\()p Fp(p;)8 b(q)r Fq(\))e(+)j Fp(d)p Fq(\()p Fp(T)d Fq(\()p Fp(p)p Fq(\))p Fp(;)i(q)r Fq(\))0 2072 y(whic)o(h)16 b(implies)608 2128 y Fp(nd)p Fq(\()p Fp(p;)8 b(T)e Fq(\()p Fp(p)p Fq(\)\))11 b Fj(\025)890 2088 y Fk(X)911 2175 y Fl(q)957 2128 y Fp(d)p Fq(\()p Fp(p;)d(q)r Fq(\))g(+)j Fp(d)p Fq(\()p Fp(T)6 b Fq(\()p Fp(p)p Fq(\))p Fp(;)i(q)r Fq(\))p Fp(:)0 2239 y Fq(Therefore)588 2321 y Fp(C)s Fq(\()p Fp(T)e Fq(\))40 b(=)810 2280 y Fk(X)831 2368 y Fl(p)878 2321 y Fp(d)p Fq(\()p Fp(p;)8 b(T)e Fq(\()p Fp(p)p Fq(\)\))733 2455 y Fj(\024)810 2414 y Fk(X)831 2502 y Fl(p)885 2424 y Fq(1)p 883 2444 28 2 v 883 2486 a Fp(n)923 2414 y Fk(X)944 2502 y Fl(q)990 2455 y Fp(d)p Fq(\()p Fp(p;)i(q)r Fq(\))g(+)j Fp(d)p Fq(\()p Fp(T)6 b Fq(\()p Fp(p)p Fq(\))p Fp(;)i(q)r Fq(\))733 2589 y(=)818 2558 y(2)p 815 2578 V 815 2620 a Fp(n)855 2548 y Fk(X)876 2636 y Fl(p)923 2548 y Fk(X)944 2636 y Fl(q)990 2589 y Fp(d)p Fq(\()p Fp(p;)g(q)r Fq(\))733 2700 y Fj(\024)42 b Fq(2)p Fp(E)s Fq([)p Fp(C)s Fq(\()p Fp(T)970 2681 y Fz(0)980 2700 y Fq(\)])964 2825 y(8)p eop %%Page: 9 9 9 8 bop 1916 46 a Fa(2)71 113 y Fq(Th)o(us)15 b(b)o(y)g(Lemmas)g(2)g (and)g(3)g(w)o(e)g(ha)o(v)o(e)g(the)g(follo)o(wing)h(theorem.)0 209 y Ff(Theorem)h(3)23 b Fg(F)m(or)16 b(any)g Fp(\016)e(>)f Fq(0)j Fg(ther)n(e)h(is)e(a)771 191 y Fm(1)p Fz(\000)p Fl(\016)p 771 198 62 2 v 793 225 a Fm(2)838 209 y Fg(-appr)n(oximation) i(algorithm)g(for)g(MaxTSP)e(running)h(in)f Fp(O)q Fq(\()1906 191 y Fl(n)p 1906 198 22 2 v 1908 225 a(\016)1932 209 y Fq(\))0 266 y Fg(time.)0 407 y Fr(7)67 b(Minim)n(um)24 b(Routing)g(Cost)d(Spanning)j(T)-6 b(ree)0 509 y Fq(In)17 b(this)f(section)h(w)o(e)f(describ)q(e)i(the)e(appro)o(ximation)g (algorithm)g(for)f(the)i(MR)o(CST)e(problem.)24 b(The)16 b(algorithm)0 565 y(pro)q(ceeds)i(b)o(y)f(c)o(ho)q(osing)h Fp(q)g Fj(2)e Fp(X)21 b Fq(at)16 b(random)h(and)g(rep)q(orting)h(a)f (star)f Fp(S)1261 572 y Fl(q)1297 565 y Fq(ro)q(oted)h(at)g(that)f(v)o (ertex.)26 b(Belo)o(w)17 b(w)o(e)0 622 y(sho)o(w)d(that)g(the)g (probabilit)o(y)i(the)f(cost)f Fp(C)s Fq(\()p Fp(S)772 629 y Fl(q)790 622 y Fq(\))g(exceeds)h Fp(C)h Fq(=)d(2)1112 590 y Fk(P)1155 633 y Fl(p;q)1209 622 y Fp(d)p Fq(\()p Fp(p;)8 b(q)r Fq(\)\(1)e(+)j Fp(\016)r Fq(\))14 b(is)h(at)f(most)g(1)8 b Fj(\000)1793 604 y Fm(1)p 1771 611 62 2 v 1771 637 a(1+)p Fl(\016)1838 622 y Fq(,)14 b(th)o(us)0 678 y(b)o(y)h(rep)q (eating)g(this)h(pro)q(cedure)f Fp(O)q Fq(\(1)p Fp(=\016)r Fq(\))f(times)h(and)g(taking)g(b)q(est)g(star)f(w)o(e)h(obtain)g(a)f (constan)o(t)g(probabilit)o(y)i(of)0 735 y(success.)71 791 y(The)i(probabilit)o(y)i(b)q(ound)f(is)g(obtained)g(as)f(follo)o (ws.)30 b(Consider)19 b(the)f(exp)q(ectation)h Fp(E)s Fq([)p Fp(C)s Fq(\()p Fp(S)1675 798 y Fl(q)1692 791 y Fq(\)].)29 b(W)l(e)18 b(kno)o(w)0 847 y(that)585 947 y Fp(E)s Fq([)p Fp(C)s Fq(\()p Fp(S)717 954 y Fl(q)734 947 y Fq(\)])41 b Fj(\024)890 917 y Fq(1)p 888 937 28 2 v 888 978 a Fp(n)928 907 y Fk(X)949 994 y Fl(q)995 947 y Fp(C)s Fq(\()p Fp(S)1077 954 y Fl(q)1095 947 y Fq(\))806 1081 y(=)890 1051 y(1)p 888 1071 V 888 1112 a Fp(n)928 1041 y Fk(X)949 1128 y Fl(q)995 1041 y Fk(X)1003 1128 y Fl(p;r)1063 1081 y Fp(d)p Fq(\()p Fp(p;)8 b(q)r Fq(\))g(+)i Fp(d)p Fq(\()p Fp(q)r(;)e(r)q Fq(\))806 1200 y(=)42 b(2)914 1159 y Fk(X)921 1247 y Fl(p;r)981 1200 y Fp(d)p Fq(\()p Fp(p;)8 b(r)q Fq(\))0 1329 y(The)15 b(probabilit)o(y)i(b)q(ound)f(follo)o(ws)f(b)o(y)g(Mark)o(o)o(v)f (inequalit)o(y)l(.)0 1470 y Fr(8)67 b(Av)n(erage)22 b(Distance)0 1572 y Fq(In)17 b(this)h(section)f(w)o(e)f(giv)o(e)h(an)g(appro)o (ximation)g(algorithm)g(for)f(the)h(Av)o(erage)f(Distance)h(problem.)25 b(The)17 b(algo-)0 1628 y(rithm)h(\014nds)h(the)f(v)m(alue)i(of)d(the)i (sum)f(of)g(all)h(the)f(distances)h(\(call)g(it)f Fp(A)p Fq(\))g(with)h(m)o(ultiplicativ)o(e)h(error)e(\(1)11 b(+)h Fp(\016)r Fq(\))0 1685 y(in)18 b(time)f Fp(O)q Fq(\()p Fp(n=\016)286 1668 y Fm(7)p Fl(=)p Fm(2)340 1685 y Fq(\).)24 b(The)17 b(actual)g(algorithm)g(is)g(simple)i(-)e(w)o(e)f (sample)h(a)g(set)f Fp(S)k Fq(\(of)c(cardinalit)o(y)i Fp(s)d Fq(=)h Fp(an)p Fq(\))g(of)0 1741 y(edges)i(b)o(y)g(includin)q(g) i(eac)o(h)e(edge)h(with)f(probabilit)o(y)956 1723 y Fl(s)p 949 1730 32 2 v 949 1757 a(m)985 1741 y Fq(,)g(compute)h(the)f(sum)g (of)g(their)g(length)h(and)f(m)o(ultiply)0 1797 y(b)o(y)71 1780 y Fl(m)p 71 1787 V 79 1813 a(s)107 1797 y Fq(,)h(where)f Fp(m)g Fq(=)383 1763 y Fk(\000)402 1777 y Fl(n)404 1813 y Fm(2)424 1763 y Fk(\001)443 1797 y Fq(.)29 b(The)18 b(running)h(time)g(of)e(the)i(algorithm)f(is)g(clearly)i Fp(O)q Fq(\()p Fp(s)p Fq(\))d(with)i(high)g(probabilit)o(y)l(.)0 1859 y(Belo)o(w)g(w)o(e)f(pro)o(v)o(e)g(that)g(for)f Fp(s)i Fq(=)f Fp(O)q Fq(\()p Fp(n=\016)727 1842 y Fm(7)p Fl(=)p Fm(2)782 1859 y Fq(\))g(the)g(result)h(is)g(a)f(go)q(o)q(d)h (appro)o(ximation)f(of)g Fp(A)p Fq(.)30 b(Note)18 b(that)g(the)0 1915 y(assumption)c(of)g(\()p Fp(X)q(;)8 b(d)p Fq(\))k(b)q(eing)j(a)f (metric)g(is)h(crucial)g(for)f(this)g(result:)20 b(otherwise)14 b(one)g(could)h(assign)f(arbitrarily)0 1972 y(large)20 b(w)o(eigh)o(t)g(\(sa)o(y)e Fp(w)q Fq(\))i(to)f(one)h(edge,)h(whic)o(h) g(w)o(ould)f(not)g(b)q(e)g(included)j(in)d Fp(S)j Fq(with)d(high)h (probabilit)o(y)g(and)0 2028 y(th)o(us)15 b(the)h(estimation)g(of)f Fp(A)h Fq(w)o(ould)g(b)q(e)g(incorrect.)21 b(The)16 b(metric)g(space)g (assumption)g(allo)o(ws)g(us)f(to)g(a)o(v)o(oid)h(this)0 2085 y(problem,)e(as)f(w)o(e)h(kno)o(w)f(that)g(if)h Fp(d)p Fq(\()p Fp(p;)8 b(q)r Fq(\))i Fp(>)j(w)i Fq(then)f(for)f(eac)o (h)g Fp(a)g Fj(2)g Fp(X)k Fq(either)d Fp(d)p Fq(\()p Fp(p;)8 b(x)p Fq(\))k(or)h Fp(d)p Fq(\()p Fp(q)r(;)8 b(x)p Fq(\))j(is)j(greater)f(than)0 2141 y Fp(w)q(=)p Fq(2,)h(th)o(us)h(with)h(a)e(go)q(o)q(d)i(probabilit)o(y)g(w)o(e)f(hit) h(one)f(of)g(these)g(edges.)71 2197 y(Let)j(\001)g(b)q(e)h(the)f (diameter)h(of)f(the)g(metric)h(and)f(assume)g(that)g(the)g(minim)o(um) i(in)o(terp)q(oin)o(t)f(distance)g(is)g(1.)0 2254 y(Let)f Fp(c)e Fq(=)h(1)12 b(+)g Fp(\017)p Fq(,)18 b(for)f(some)h(0)e Fp(<)h(\017)h(<)f(\016)r Fq(.)27 b(Split)19 b(the)f(in)o(terv)m(al)h ([1)8 b Fp(:)g(:)g(:)t Fq(\001])17 b(of)g(p)q(ossible)j(distances)e(in) o(to)g(in)o(terv)m(als)0 2310 y Fp(I)20 2317 y Fl(i)47 2310 y Fq(=)13 b([)p Fp(c)128 2294 y Fl(i)141 2310 y Fp(;)8 b(c)182 2294 y Fl(i)p Fm(+1)240 2310 y Fq(\),)15 b(for)f Fp(i)e Fj(\025)h Fq(0.)20 b(Let)15 b Fp(n)595 2317 y Fl(i)625 2310 y Fq(b)q(e)h(the)f(n)o(um)o(b)q(er)h(of)e (distances)i(falling)h(in)o(to)e(in)o(terv)m(al)h Fp(I)1591 2317 y Fl(i)1620 2310 y Fq(and)g(let)f Fp(s)1795 2317 y Fl(i)1825 2310 y Fq(b)q(e)h(the)0 2367 y(n)o(um)o(b)q(er)f(of)e (distances)i(from)f Fp(S)i Fq(falling)g(in)o(to)e Fp(I)808 2374 y Fl(i)822 2367 y Fq(.)20 b(De\014ne)1007 2355 y(~)995 2367 y Fp(A)12 b Fq(=)1089 2335 y Fk(P)1133 2378 y Fl(i)1155 2367 y Fp(c)1175 2350 y Fl(i)1189 2367 y Fp(n)1216 2374 y Fl(i)1230 2367 y Fq(,)i Fp(A)1291 2350 y Fz(0)1315 2367 y Fq(=)1363 2335 y Fk(P)1407 2378 y Fl(e)p Fz(2)p Fl(S)1480 2367 y Fp(d)p Fq(\()p Fp(e)p Fq(\))f(and)1673 2355 y(~)1662 2367 y Fp(A)1696 2354 y Fz(0)1720 2367 y Fq(=)1773 2349 y Fl(m)p 1773 2356 V 1781 2382 a(s)1817 2335 y Fk(P)1868 2367 y Fp(c)1888 2350 y Fl(i)1902 2367 y Fp(s)1923 2374 y Fl(i)1937 2367 y Fq(.)0 2429 y(Clearly)l(,)18 b Fp(A)e Fq(=)281 2418 y(~)269 2429 y Fp(A)q Fq(\(1)10 b Fj(\006)i Fp(\017)p Fq(\))17 b(and)g Fp(A)579 2413 y Fz(0)606 2429 y Fq(=)669 2417 y(~)657 2429 y Fp(A)691 2416 y Fz(0)703 2429 y Fq(\(1)10 b Fj(\006)i Fp(\017)p Fq(\),)17 b(th)o(us)g(it)g(is)g(su\016cien)o(t)h(to)e(sho)o(w)h(that) 1539 2417 y(~)1528 2429 y Fp(A)1562 2416 y Fz(0)1591 2429 y Fq(w)o(ell)g(appro)o(ximates)12 2474 y(~)0 2485 y Fp(A)p Fq(.)30 b(T)l(o)19 b(this)g(end)g(notice)g(that)f Fp(E)s Fq([)628 2473 y(~)618 2485 y Fp(A)652 2472 y Fz(0)663 2485 y Fq(])g(=)759 2474 y(~)747 2485 y Fp(A)p Fq(,)i(th)o(us)e(it)h (is)g(su\016cien)o(t)g(to)f(b)q(ound)i(the)f(v)m(ariance)g(of)1742 2473 y(~)1730 2485 y Fp(A)1764 2472 y Fz(0)1795 2485 y Fq(and)g(use)0 2542 y(Cheb)o(yshev)d(inequalit)o(y)l(.)22 b(The)15 b(v)m(ariance)h Fp(D)764 2525 y Fm(2)784 2542 y Fq([)808 2530 y(~)797 2542 y Fp(A)831 2529 y Fz(0)842 2542 y Fq(])f(can)g(b)q(e)h(b)q(ounded)h(b)o(y)691 2631 y Fp(m)731 2614 y Fm(2)p 691 2651 60 2 v 700 2693 a Fp(s)721 2680 y Fm(2)763 2621 y Fk(X)787 2712 y Fl(i)831 2662 y Fp(c)851 2643 y Fm(2)p Fl(i)882 2662 y Fp(n)909 2669 y Fl(i)938 2631 y Fp(s)p 928 2651 40 2 v 928 2693 a(m)986 2662 y Fq(=)1039 2631 y Fp(m)p 1039 2651 V 1048 2693 a(s)1091 2621 y Fk(X)1159 2662 y Fp(c)1179 2643 y Fm(2)p Fl(i)1210 2662 y Fp(n)1237 2669 y Fl(i)1252 2662 y Fp(:)964 2825 y Fq(9)p eop %%Page: 10 10 10 9 bop 71 46 a Fq(Th)o(us)15 b(b)o(y)g(Cheb)o(yshev)h(inequalit)o(y)g (w)o(e)f(get)647 148 y Fp(P)48 b Fq(=)42 b(Pr)o([)p Fj(j)886 136 y Fq(~)875 148 y Fp(A)909 135 y Fz(0)931 148 y Fj(\000)10 b Fp(E)s Fq([)1036 136 y(~)1026 148 y Fp(A)1060 135 y Fz(0)1071 148 y Fq(])i Fj(\025)h Fp(\017)d Fj(\001)g Fp(E)s Fq([)1256 136 y(~)1245 148 y Fp(A)o Fq(]])724 236 y Fj(\024)866 205 y Fq(1)p 806 225 144 2 v 811 262 a Fl(\017)825 252 y Fh(2)842 262 y Fl(E)870 252 y Fh(2)887 262 y Fm([)907 253 y(~)897 262 y Fl(A)923 252 y Fo(0)935 262 y Fm(])p 811 273 134 2 v 825 306 a Fl(D)855 297 y Fh(2)873 306 y Fm([)892 297 y(~)883 306 y Fl(A)909 297 y Fo(0)920 306 y Fm(])724 404 y Fq(=)823 373 y Fp(D)862 357 y Fm(2)882 373 y Fq([)906 361 y(~)895 373 y Fp(A)929 360 y Fz(0)940 373 y Fq(])p 806 394 166 2 v 806 441 a Fp(\017)824 428 y Fm(2)844 441 y Fp(E)881 428 y Fm(2)900 441 y Fq([)924 429 y(~)913 441 y Fp(A)947 428 y Fz(0)958 441 y Fq(])71 544 y(As)15 b Fp(E)175 528 y Fm(2)194 544 y Fq([)218 532 y(~)207 544 y Fp(A)241 531 y Fz(0)252 544 y Fq(])d Fj(\025)325 512 y Fk(P)377 544 y Fp(c)397 528 y Fm(2)p Fl(i)428 544 y Fp(n)455 528 y Fm(2)455 557 y Fl(i)475 544 y Fq(,)j(it)g(is)h(su\016cien)o(t)g(to)e(b)q(ound)j (from)d(the)h(ab)q(o)o(v)o(e)g(the)g(ratio)841 676 y Fp(F)k Fq(=)945 613 y Fk(P)996 645 y Fp(c)1016 628 y Fm(2)p Fl(i)1047 645 y Fp(n)1074 652 y Fl(i)p 942 665 150 2 v 942 675 a Fk(P)993 707 y Fp(c)1013 694 y Fm(2)p Fl(i)1045 707 y Fp(n)1072 691 y Fm(2)1072 720 y Fl(i)1097 676 y Fp(:)71 804 y Fq(In)d(order)g(to)f(do)h(this)g(w)o(e)g(mak)o(e)f (the)h(follo)o(wing)h(observ)m(ation)f(\(this)g(is)h(the)f(only)g (place)h(where)f(w)o(e)g(use)g(the)0 860 y(fact)i(that)h Fp(d)f Fq(is)i(a)f(metric\).)31 b(Let)19 b Fp(a;)8 b(b)18 b Fj(2)h Fp(X)k Fq(b)q(e)c(a)g(pair)g(of)g(p)q(oin)o(ts)g(suc)o(h)h (that)e Fp(d)p Fq(\()p Fp(a;)8 b(b)p Fq(\))17 b(=)i(\001.)31 b(Then)20 b(for)e(an)o(y)0 917 y Fp(p)e Fj(2)g Fp(X)21 b Fq(w)o(e)c(kno)o(w)f(that)h Fp(d)p Fq(\()p Fp(a;)8 b(p)p Fq(\))h(+)j Fp(d)p Fq(\()p Fp(p;)c(b)p Fq(\))14 b Fj(\025)i Fq(\001,)h(th)o(us)g(at)g(least)g(one)h(of)f Fp(d)p Fq(\()p Fp(a;)8 b(p)p Fq(\))15 b(and)i Fp(d)p Fq(\()p Fp(p;)8 b(b)p Fq(\))15 b(is)j(greater)e(than)0 973 y(\001)p Fp(=)p Fq(2.)28 b(Let)18 b Fp(k)h Fq(b)q(e)g(suc)o(h)f (that)f Fp(c)543 957 y Fl(k)582 973 y Fq(=)g(\001.)29 b(By)18 b(pigeonhole)h(principle)i(there)d(exists)h(0)e Fj(\024)h Fp(j)h Fj(\024)f Fq(log)1696 984 y Fl(c)1721 973 y Fq(2)f(suc)o(h)i(that)0 1030 y Fp(n)27 1037 y Fl(k)q Fz(\000)p Fl(j)105 1030 y Fj(\025)13 b Fp(n=)8 b Fq(log)269 1041 y Fl(c)294 1030 y Fq(2.)19 b(This)c(enables)g(us)g(to)e(b)q(ound)i Fp(F)21 b Fq(as)14 b(follo)o(ws.)19 b(Let)c Fp(P)k Fq(=)13 b Fj(f)p Fp(i)f Fq(:)g Fp(n)1412 1037 y Fl(i)1439 1030 y Fj(\025)h Fp(t)p Fj(g)8 b(\000)h(f)p Fp(k)g Fj(\000)f Fp(j)s Fj(g)13 b Fq(for)h Fp(t)f Fq(=)g Fp(\013n)p Fq(,)0 1086 y(where)18 b Fp(\013)g Fq(is)g(c)o(hosen)g(later.)28 b(W)l(e)18 b(can)g(write)g Fp(F)24 b Fq(as)917 1068 y Fl(N)945 1073 y Fh(1)962 1068 y Fm(+)p Fl(N)1017 1073 y Fh(2)p 911 1076 130 2 v 911 1102 a Fl(M)945 1107 y Fh(1)962 1102 y Fm(+)p Fl(M)1023 1107 y Fh(2)1046 1086 y Fq(,)18 b(where)g Fp(M)1255 1093 y Fm(1)1292 1086 y Fq(=)1344 1054 y Fk(P)1388 1098 y Fl(i)p Fz(2)p Fl(P)1460 1086 y Fp(c)1480 1070 y Fm(2)p Fl(i)1512 1086 y Fp(n)1539 1070 y Fm(2)1539 1098 y Fl(i)1559 1086 y Fq(,)g Fp(M)1634 1093 y Fm(2)1670 1086 y Fq(=)1723 1054 y Fk(P)1767 1098 y Fl(i)t(=)-22 b Fz(2)o Fl(P)1839 1086 y Fp(c)1859 1070 y Fm(2)p Fl(i)1890 1086 y Fp(n)1917 1070 y Fm(2)1917 1098 y Fl(i)1937 1086 y Fq(,)0 1149 y Fp(N)37 1156 y Fm(1)69 1149 y Fq(=)117 1117 y Fk(P)161 1161 y Fl(i)p Fz(2)p Fl(P)233 1149 y Fp(c)253 1133 y Fm(2)p Fl(i)285 1149 y Fp(n)312 1156 y Fl(i)341 1149 y Fq(and)15 b Fp(N)466 1156 y Fm(2)498 1149 y Fq(=)546 1117 y Fk(P)590 1161 y Fl(i)t(=)-22 b Fz(2)p Fl(P)663 1149 y Fp(c)683 1133 y Fm(2)p Fl(i)714 1149 y Fp(n)741 1156 y Fl(i)755 1149 y Fq(.)71 1206 y(No)o(w)14 b(w)o(e)h(observ)o(e)g(that)509 1187 y Fl(N)537 1192 y Fh(1)p 506 1195 52 2 v 506 1221 a Fl(M)540 1226 y Fh(1)575 1206 y Fj(\024)628 1188 y Fm(1)p 628 1195 18 2 v 630 1221 a Fl(t)666 1206 y Fq(\(from)f(the)h (de\014nition\))i(and)588 1348 y Fp(N)625 1355 y Fm(2)657 1348 y Fj(\024)c Fp(t)729 1307 y Fk(X)796 1348 y Fp(c)816 1329 y Fm(2)p Fl(i)860 1348 y Fj(\024)g Fp(t)929 1317 y(c)949 1301 y Fm(2\()p Fl(k)q Fm(+1\))p 929 1337 132 2 v 936 1379 a Fp(c)956 1366 y Fm(2)986 1379 y Fj(\000)d Fq(1)1078 1348 y Fj(\024)1131 1317 y Fq(\001)1169 1301 y Fm(2)1189 1317 y Fq(\(1)f(+)i Fp(\017)p Fq(\))1321 1301 y Fm(2)p 1131 1337 210 2 v 1227 1379 a Fp(\017)1346 1348 y(t)0 1464 y Fq(while)802 1530 y Fp(M)846 1537 y Fm(2)878 1530 y Fj(\025)i Fq(\()949 1499 y(\001)p 949 1520 38 2 v 957 1561 a(2)1038 1499 y Fp(n)p 997 1520 109 2 v 997 1564 a Fq(log)1056 1546 y Fm(2)1056 1576 y Fl(c)1083 1564 y Fq(2)1111 1530 y(\))1129 1511 y Fm(2)0 1638 y Fq(th)o(us)727 1682 y Fp(N)764 1689 y Fm(2)p 723 1702 64 2 v 723 1744 a Fp(M)767 1751 y Fm(2)804 1713 y Fj(\024)859 1682 y Fq(1)p 857 1702 28 2 v 857 1744 a Fp(n)894 1682 y Fq(4)8 b(log)983 1664 y Fm(2)983 1693 y Fl(c)1011 1682 y Fq(2)p Fp(\013)p Fq(\(1)h(+)i Fp(\017)p Fq(\))1195 1666 y Fm(2)p 894 1702 321 2 v 1045 1744 a Fp(\017)1220 1713 y(:)0 1814 y Fq(Therefore)476 1888 y Fp(F)19 b Fj(\024)13 b Fq(max)o(\()683 1858 y Fp(N)720 1865 y Fm(1)p 679 1878 64 2 v 679 1920 a Fp(M)723 1927 y Fm(1)748 1888 y Fp(;)777 1858 y(N)814 1865 y Fm(2)p 773 1878 V 773 1920 a Fp(M)817 1927 y Fm(2)842 1888 y Fq(\))f(=)927 1858 y(1)p 925 1878 28 2 v 925 1920 a Fp(n)965 1888 y Fq(max\()1073 1858 y(4)c(log)1161 1839 y Fm(2)1161 1869 y Fl(c)1189 1858 y Fq(2\(1)h(+)h Fp(\017)p Fq(\))1343 1841 y Fm(2)p 1073 1878 291 2 v 1208 1920 a Fp(\017)1368 1888 y(\013;)1426 1858 y Fq(1)p 1422 1878 30 2 v 1422 1920 a Fp(\013)1457 1888 y Fq(\))0 1999 y(and)15 b(b)o(y)h(setting)f Fp(\013)e Fq(=)g(\002\()p Fp(\017)462 1982 y Fm(3)p Fl(=)p Fm(2)517 1999 y Fq(\))i(w)o(e)g(obtain)g(that)g Fp(F)k Fq(=)13 b Fp(O)q Fq(\()1034 1981 y Fm(1)p 1012 1988 63 2 v 1012 2019 a Fl(\017)1026 2009 y Fh(3)p Fi(=)p Fh(2)1086 1981 y Fm(1)p 1084 1988 22 2 v 1084 2015 a Fl(n)1111 1999 y Fq(\).)19 b(Th)o(us)657 2128 y Fp(P)g Fq(=)13 b Fp(O)q Fq(\()819 2098 y(1)p 812 2118 39 2 v 812 2160 a Fp(\017)830 2146 y Fm(2)865 2098 y Fp(m)p 859 2118 52 2 v 859 2160 a(an)946 2098 y Fq(1)p 921 2118 74 2 v 921 2161 a Fp(\017)939 2148 y Fm(3)p Fl(=)p Fm(2)1006 2098 y Fq(1)p 1004 2118 28 2 v 1004 2160 a Fp(n)1036 2128 y Fq(\))g(=)g Fp(O)q Fq(\()1211 2098 y(1)p 1174 2118 98 2 v 1174 2161 a Fp(a\017)1216 2148 y Fm(7)p Fl(=)p Fm(2)1276 2128 y Fq(\))0 2250 y(and)g(b)o(y)f(setting)h Fp(\017)g Fq(=)g(\002\()p Fp(\016)r Fq(\))f(and)h Fp(a)f Fq(=)h Fp(O)q Fq(\()730 2232 y Fm(1)p 706 2239 66 2 v 706 2270 a Fl(\016)723 2260 y Fh(7)p Fi(=)p Fh(2)776 2250 y Fq(\))f(w)o(e)g(pro)o(v)o(e)g(the)h(appro)o(ximation)g(b)q (ound.)19 b(In)14 b(this)f(w)o(a)o(y)e(w)o(e)h(pro)o(v)o(ed)0 2307 y(the)j(follo)o(wing)h(Theorem.)0 2413 y Ff(Theorem)h(4)23 b Fg(F)m(or)17 b(any)h Fp(\016)f(>)f Fq(0)p Fg(,)h(ther)n(e)h(is)g(a)f Fq(\(1)11 b(+)h Fp(\016)r Fq(\))p Fg(-appr)n(oximation)18 b(algorithm)h(for)f(the)g(A)o(ver)n(age)f(Distanc)n(e)0 2469 y(pr)n(oblem)f(running)g(in)f Fp(O)q Fq(\()478 2451 y Fl(n)p 456 2458 V 456 2489 a(\016)473 2479 y Fh(7)p Fi(=)p Fh(2)526 2469 y Fq(\))h Fg(time.)952 2825 y Fq(10)p eop %%Page: 11 11 11 10 bop 357 2 1237 2 v 357 10 V 356 66 2 57 v 365 66 V 390 49 a Fq(problem)p 761 66 V 235 w(appro)o(x.)20 b(factor)p 1095 66 V 49 w(not)14 b(ac)o(hiev)m(able)k(in)e(time)p 1584 66 V 1593 66 V 357 68 1237 2 v 356 125 2 57 v 365 125 V 390 108 a(Closest)f(P)o(air)p 761 125 V 156 w(an)o(y)p 1095 125 V 264 w Fp(o)p Fq(\()p Fp(n)1188 91 y Fm(2)1207 108 y Fq(\))p 1584 125 V 1593 125 V 356 181 V 365 181 V 390 164 a(F)l(urthest)g(P)o(air)p 761 181 V 130 w Fp(>)839 146 y Fm(1)p 839 153 18 2 v 839 180 a(2)p 1095 181 2 57 v 1121 164 a Fp(o)p Fq(\()p Fp(n)1188 148 y Fm(2)1207 164 y Fq(\))p 1584 181 V 1593 181 V 356 237 V 365 237 V 390 221 a(MaxST/MaxTSP)p 761 237 V 48 w Fp(>)839 203 y Fm(1)p 839 210 18 2 v 839 236 a(2)p 1095 237 2 57 v 1121 221 a Fp(o)p Fq(\()p Fp(n)1188 204 y Fm(2)1207 221 y Fq(\))p 1584 237 V 1593 237 V 356 294 V 365 294 V 390 277 a(MinST/MinTSP)p 761 294 V 68 w Fp(O)q Fq(\(1\))p 1095 294 V 240 w Fp(o)p Fq(\()p Fp(n)1188 260 y Fm(2)1207 277 y Fq(\))p 1584 294 V 1593 294 V 357 296 1237 2 v 482 373 a(T)l(able)h(2:)k(Lo)o(w)o(er)14 b(b)q(ounds)i(for)f(metric)h (space)f(problems)0 510 y Fr(9)67 b(Lo)n(w)n(er)22 b(b)r(ounds)0 612 y Fq(In)14 b(this)h(section)f(w)o(e)g(in)o(v)o(estigate)g (limitations)h(of)e(sublinear)j(time)e(algorithms)g(in)h(metric)f (spaces.)19 b(Our)c(results)0 668 y(are)c(depicted)i(in)g(the)e(T)l (able)i(9;)f(they)f(hold)i(for)e(randomized)h(algorithms.)19 b(When)12 b(com)o(bined)g(with)g(our)f(b)q(ounds,)0 725 y(one)16 b(can)g(observ)o(e)g(in)o(teresting)g(phenomenon:)22 b(the)16 b(minimization)i(problems)f(are)e(di\016cult)j(to)d(appro)o (ximate,)0 781 y(while)j(the)e(maximization)h(problems)g(are)f(appro)o (ximable)h(to)f(within)i(a)e(small)h(constan)o(t)e(factor.)22 b(In)o(tuitiv)o(ely)l(,)0 838 y(this)c(is)g(due)g(to)f(the)g(fact)g (that)g(small)h(distances)g(can)f(b)q(e)i(easily)f(\\hidden")h(in)f (the)f(metric)h(space,)g(while)h(the)0 894 y(triangle)d(inequalit)o(y)h (prev)o(en)o(ts)e(large)g(distances)h(from)e(\\hiding".)71 951 y Ff(Pro)q(of:)19 b Fq(The)d(pro)q(ofs)e(are)h(as)g(follo)o(ws)0 1044 y Ff(Closest)i(pair)24 b Fq(:)19 b(Set)d(all)g(distances)g(to)e(1) h(except)h(for)e(one)i(edge)f(c)o(hosen)h(at)e(random,)h(whic)o(h)h(is) g(set)e(to)h Fp(\017)e(>)g Fq(0)0 1138 y Ff(F)l(urthest)k(pair)23 b Fq(:)d(Set)15 b(all)h(distances)g(to)f(1)g(except)g(for)g(one)g(edge) h(c)o(hosen)f(at)g(random,)f(whic)o(h)i(is)g(set)f(to)f(2)0 1232 y Ff(MaxST/MaxTSP)23 b Fq(:)i(Set)18 b(all)h(distances)g(to)f(1)g (except)g(for)g(edges)g(on)g(a)g(random)g(path)f(of)h(length)h Fp(n)12 b Fj(\000)h Fq(1,)114 1288 y(whic)o(h)h(are)g(set)g(to)f(2.)19 b(The)c(optimal)f(cost)g(of)f(b)q(oth)h(MaxST)g(and)g(MaxTSP)f(is)i (\(2)7 b Fj(\000)h Fp(\017)p Fq(\))p Fp(n)p Fq(,)14 b(but)g(\014nding)i Fp(\016)r(n)114 1345 y Fq(edges)f(set)g(to)g(2)f(for)h(an)o(y)g (\014xed)h Fp(\016)e(>)f Fq(0)i(requires)h(\012\()p Fp(n)1034 1328 y Fm(2)1054 1345 y Fq(\))e(time.)0 1439 y Ff(MinST/MinTSP)24 b Fq(:)i(F)l(or)17 b(an)o(y)h Fp(B)i Fq(=)e Fp(O)q Fq(\(1\))f(c)o(ho)q (ose)h(a)g(random)g(path)g(of)g(length)h Fp(n)12 b Fj(\000)g Fq(1,)19 b(set)f(all)h(edges)f(on)114 1495 y(that)c(path)g(to)g(1)h (and)g(consider)g(the)g(metric)g(obtained)g(b)o(y)g(taking)g(the)g (shortest)e(paths)i(metric)g(induced)114 1552 y(b)o(y)g(the)h(unit)h (edges)f(and)g(limiting)i(the)d(maxim)o(um)h(distance)h(to)e(some)g Fp(B)r Fq(.)23 b(One)16 b(can)g(observ)o(e)g(that)f(the)114 1608 y(optim)o(um)e(solution)i(has)e(cost)g Fp(n)7 b Fq(+)g Fp(B)r Fq(.)21 b(On)14 b(the)g(other)f(hand,)h(\014nding)h Fp(\016)r(n)f Fq(edges)g(with)g(cost)f Fp(<)g(B)j Fq(for)d(an)o(y)114 1664 y(\014xed)i Fp(\016)g(>)e Fq(0)i(requires)h(\012\()p Fp(n)593 1648 y Fm(2)612 1664 y Fp(=B)r Fq(\))g(time.)1916 1758 y Fa(2)0 1827 y Ff(Ac)o(kno)o(wledgmen)o(ts:)23 b Fq(The)17 b(author)g(w)o(ould)h(lik)o(e)h(to)e(thank)h(Ashish)g(Go)q (el,)g(Ho)o(w)o(ard)f(Karlo\013)g(and)h(Sudipto)0 1884 y(Guha)d(for)g(helpful)i(commen)o(ts.)0 2027 y Fr(References)23 2128 y Fq([1])k(A.)15 b(Boro)q(din,)g(R.)g(Ostro)o(vsky)l(,)e(Y.)i (Rabani,)g(\\Sub)q(quadratic)h(Appro)o(ximation)f(Algorithms)g(F)l(or)f (Cluster-)93 2185 y(ing)i(Problems)g(in)g(High)g(Dimensional)g (Spaces",)f(STOC'99.)23 2279 y([2])21 b(M.)f(Charik)m(ar,)i(S.)f(Guha,) g(\\Impro)o(v)o(ed)g(Com)o(binatorial)g(Algorithms)g(for)f(the)h(F)l (acilit)o(y)g(Lo)q(cation)h(and)93 2335 y(k-Median)16 b(Problems",)f(F)o(OCS'99.)23 2429 y([3])21 b(M.)f(Charik)m(ar,)i(S.)e (Guha,)i(E.)e(T)l(ardos,)h(D.)f(Shmo)o(ys,)h(\\A)f(Constan)o(t)g(F)l (actor)f(Appro)o(ximation)i(for)f(the)93 2485 y(k-Median)c(Problem",)f (STOC'99.)23 2579 y([4])21 b(D.R.)13 b(Cutting,)g(D.R.)g(Karger,)f (J.O.)h(P)o(edersen)h(and)f(J.W.)f(T)l(uk)o(ey)l(,)i(\\Scatter/Gather:) j(A)c(Cluster-based)93 2636 y(Approac)o(h)j(to)e(Bro)o(wsing)h(Large)g (Do)q(cumen)o(t)g(Collections",)h(SIGIR'92.)952 2825 y(11)p eop %%Page: 12 12 12 11 bop 23 46 a Fq([5])21 b(E.)g(Cohen,)i(D.)d(Lewis,)j(\\Appro)o (ximating)f(matrix)e(m)o(ultiplication)k(for)d(pattern)f(recognition)i (tasks",)93 102 y(SOD)o(A'97,)14 b(pp.)i(682-691.)23 191 y([6])21 b(F.Ergun,)33 b(S.Kannan,)i(S.R.Kumar,)e(R.)e(Rubinfeld)i (and)e(M.)e(Visw)o(anathan,)34 b(\\Sp)q(ot-Chec)o(k)o(ers",)93 247 y(STOC'98,)15 b(pp.)g(259-268.)23 336 y([7])21 b(O.)e(Goldreic)o (h,)i(S.)d(Goldw)o(asser)g(and)h(D.)g(Ron,)g(\\Prop)q(ert)o(y)f (testing)h(and)g(its)g(connection)h(to)e(Learning)93 392 y(and)e(Appro)o(ximation",)f(F)o(OCS'96,)e(pp.)j(339-348.)23 481 y([8])21 b(W.)14 b(B.)f(F)l(rak)o(es,)g(R.)h(Baeza-Y)l(ates,)g Fg(Information)h(R)n(etrieval)g(-)g(Data)h(Structur)n(es)f(and)g(A)o (lgorithms)p Fq(,)f(Pren-)93 537 y(tice)i(Hall,)g(New)f(Jersey)l(,)h (1992.)23 625 y([9])21 b(D.)27 b(Gus\014eld,)j(\\E\016cien)o(t)e(metho) q(ds)f(for)f(m)o(ultiple)j(sequence)f(alignmen)o(ts)g(with)f(guaran)o (teed)g(error)93 682 y(b)q(ounds",)16 b Fg(Bul)r(letin)g(of)g (Mathematic)n(al)g(Biolo)n(gy)p Fq(,)f(55)f(\(1993\),)f(pp.)j(141-154.) 0 770 y([10])21 b(T.)11 b(Gonzales,)h(\\Clustering)g(to)f(Minimize)j (the)d(Maxim)o(um)g(In)o(ter-Cluster)h(Distance",)g Fg(The)n(or)n(etic) n(al)g(Com-)93 827 y(puter)17 b(Scienc)n(e)d Fq(38)h(\(1985\),)e(pp.)i (293-306.)0 915 y([11])21 b(D.)h(Ho)q(c)o(h)o(baum,)h(D.)e(Shmo)o(ys,)i (\\A)e(uni\014ed)j(approac)o(h)e(to)f(appro)o(ximate)g(algorithms)h (for)f(b)q(ottlenec)o(k)93 972 y(problems",)16 b Fg(Journal)g(of)g(the) h(A)o(CM)p Fq(,)d(33\(1986\),)e(pp.)j(533-550.)0 1060 y([12])21 b(P)l(.)15 b(Indyk,)g(\\On)g(Appro)o(ximate)g(Nearest)f (Neigh)o(b)q(ors)h(in)h(Non-Euclidean)h(Spaces",)e(F)o(OCS'98,)e(pp.)i (148-)93 1117 y(154.)0 1205 y([13])21 b(P)l(.)g(Indyk,)h(R.)e(Mot)o(w)o (ani,)g(\\Appro)o(ximate)h(Nearest)f(Neigh)o(b)q(ors:)30 b(T)l(o)o(w)o(ards)20 b(Remo)o(ving)h(the)f(Curse)g(of)93 1262 y(Dimensionalit)o(y",)d(STOC'98,)d(pp.)h(604-613.)0 1350 y([14])21 b(K.)13 b(Jain)g(and)f(V.)g(V)l(azirani,)h (\\Primal-Dual)g(Appro)o(ximation)g(Algorithms)f(for)g(Metric)g(F)l (acilit)o(y)h(Lo)q(cation)93 1407 y(and)j(k-Median)g(Problems",)f(F)o (OCS'99.)0 1495 y([15])21 b(J.)16 b(Klein)o(b)q(erg,)i(\\Tw)o(o)d (Algorithms)i(for)e(Nearest)h(Neigh)o(b)q(or)g(Searc)o(h)h(in)g(High)f (Dimensions",)h(STOC'97,)93 1552 y(pp.)f(599-608.)0 1640 y([16])21 b(E.)13 b(Kushilevitz,)j(R.)d(Ostro)o(vsky)l(,)g(and)g(Y.)g (Rabani,)i(\\)e(E\016cien)o(t)g(searc)o(h)g(for)g(appro)o(ximate)g (nearest)g(neigh-)93 1697 y(b)q(or)j(in)g(high)g(dimensional)h (spaces",)e(STOC'98,)f(pp.)h(614-623.)0 1785 y([17])21 b(M.)f(R.)h(Korup)q(olu,)i(C.)d(G.)g(Plaxton,)h(R.)g(Ra)s(jamaran,)f (\\Analysis)i(of)e(a)g(Lo)q(cal)i(Searc)o(h)f(Heuristic)h(for)93 1842 y(F)l(acilit)o(y)17 b(Lo)q(cation)e(Problems",)g(SOD)o(A'98,)f (pp.)i(1-10.)0 1930 y([18])21 b(S.R.)16 b(Kosara)s(ju,)d(J.K.)i(P)o (ark,)f(C.)h(Stein,)h(\\Long)f(T)l(ours)g(and)g(Short)g(Sup)q (erstrings",)g(F)o(OCS'94.)0 2019 y([19])21 b(J.)32 b(Lin,)37 b(J.S.)32 b(Vitter,)k(\\)p Fp(\017)p Fq(-Appro)o(ximations)c(with)h (Minim)o(um)g(P)o(ac)o(king)e(Constrain)o(t)h(Violation",)93 2075 y(STOC'92,)15 b(pp.)g(771-782.)0 2163 y([20])21 b(J.)h(Lin,)i(J.S.)e(Vitter,)h(\\Appro)o(ximation)e(Algorithms)h(for)f (Geometric)h(Median)g(Problems",)h(IPL)g(44)93 2220 y(\(1992\),)13 b(pp.)j(245-249.)0 2308 y([21])21 b(R.L.)16 b(Riv)o(est,)g(J.)g(V)l (uillemin,)j(\\On)d(recognizing)h(graph)e(prop)q(erties)i(from)e (adjacency)h(matrices",)f Fg(The)n(o-)93 2365 y(r)n(etic)n(al)h (Computer)h(Scienc)n(e)c Fq(3)i(\(1976\),)e(pp.)j(371-384.)0 2453 y([22])21 b(B.)15 b(Y.)f(W)l(u,)h(G.)f(Lancia,)h(V.)g(Bafna,)f(K)h (Chao,)f(R.)h(Ra)o(vi,)f(C.)h(Y.)f(T)l(ang,)g(\\A)h(P)o(olynomial)g (Time)g(Appro)o(xi-)93 2510 y(mation)g(Sc)o(heme)h(for)f(Minim)o(um)h (Routing)g(Cost)e(Spanning)j(T)l(rees",)d(SOD)o(A'98,)g(pp.)i(21-32.)0 2598 y([23])21 b(R.)16 b(W)l(ong,)f(\\W)l(orst-case)f(Analysis)i(of)f (Net)o(w)o(ork)g(Design)g(Problem)h(Heuristics",)g Fg(SIAM)f(J.)i(A)o (lg.)e(Discr.)93 2655 y(Meth.)h Fq(1)e(\(1980\),)f(pp.)j(51-63.)952 2825 y(12)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF </q)q>