ࡱ> PMNO`!s-ᘨ"CJ* _ AxڥkA߼$ۀ6""[P5zP}L [t e%ayţ_L^))~-?My7u,}*Z`e+^SvuB]%NWPg >Fl#p>|<}~.o˝#;[WSp+[WSQWn tK݅vk-DnS&c?k[' 0}Tsn`=|{&ory\ԷԇFYIlnzo)vtnB]%N:~G$Nv6>1?c8`>zB^Ksz72dcSC7Yٓ[9Ag`!Y|(Lؚ` . 'xڥkA߼dAC-Rp7b-CZ<ƓV`6 xԣ(?@R.Gu*Frħ-_ g+9' O{Bs~/'HSWYyn#tYyDhGhG;_u׽tRQ;7,O4SVSlsg@q.{:Ͻ:~nkrN꿼Cw)a΃qPG Ᏼ's--G8F aynWZNΉ[̫!S̫!^b^ >$ /}[̧^*ubm*!d>s9C`!TOp 投P `(+0"xcdd``fed``baV d,FYzP1n:,B@?b X؀깡jx|K2B* R vfRv,L ! ~ Ay bGXr @@ڈfμJȉYg>#Q lOpW` B Ma(w tpsF=.= 5.p2M%#RpeqIj.ŠV "B1h:-G3X?ZY`!i(T_6^Yb@ @CzxڕR=KP=;-JQ VT*:+l0b6qt*\t7'Q'| H#$'ޓw2@P+!wg,<56H\7|R`,tf.{}@&TdqAc hƕ;+KRsA<.E.b x.Ġt`YEpU`! 1OWryW `_0xڥSAkAۤI=T1`i4sEQBY[l`Ԗ%R˟55sczWiz,⊋[NqRZ|O|~V0qVB3[NZKK:@q[luJ}Z>.… j߲/~C}6>g4-H"įqdcunY^!\L#[~QKy N<}ݟNj}M֐| 6ow(OQR,Hz3+6m4,'uϣs=K`!@[mr@sTZc" @ xڥSKKQ>LBQE.EiҤ6̮6-Z !]~C-EM13ZX̜sC@p!}$"!!F0 - v>;ܣ6.]j5m|vze_Q`I%F!ɵ v1isGnZa#c%V~(Bgj UVNti*JNX6!o+ʇd>،`ʇ7LR1zgpg|]ˣku;˽ 7xNcN{P=i~2έdIYgؤ{2Z(Z3:{тA?&wZɢHrO SŽb]#ߋӃtq:MG?)bRdPDE$.*^pQ>pf6o߄g6C|?).q7I2ŴCЃOF"k p4G{>`!r(eKi:d@(xڥ=KAg._g4!b@E-DN Ip`.F3`BR"bga#XHPQK#fJؽyޙc0_ h`BƔ}aWuQ5K1h\{ 4QZX˭9%4L>{݄64ȭT(AW|6]\]oo-yk.{*&OPz$i} ~^K~Vz^uć! =H<ѮKgu{ ԮMy`7P~ϰEy>L<:@j.i͓ 2O[L*n o-:NiC"bƭя&1VyT8Ez4'D]KlK~QB;gsNȂbZR Hy=2Ǫ`!W4Ac;CO@(xڥ=KAgyFi! FJ!(iaDlŨ` Xk`ga# *׹Y0X7 q]@g2, ku(_օ0E\Cs[|sx5 r.H o(wc2vZxBV+.Ô;H ""|ve}8wTT*;*&gU!L[OL/Z/I%?*.Y3qLmfB O@c}5t^xm}θIy1@<%5=i3 2O[L*n oLNic"b{LcĮs{AmK>(39*of4U"T CM7s, =#Ĵ00Yq{dd`!4Voee:mU$R0, qxڥTKkSA>Ϥ'"EĀ@Q*–^bi"+.+r'R.ŅtU$EЍ?Bкp̙i !;sw!4pcТh u׾X;.NTZX@CRর^u-p9:&S M1C>\ܻi-iC -零Cߴۑ| t0z??<Lo }NkƬ3JPcHE/9WWǡ>,>=7_?$VpJGU9[]zo6vcG>I{ H`.j+dW\V;`MkMzAOK6; /?<@ qQEr>G_!˛MCR,3UyKfyoz}51^7Mn#VRisσ6HLANnX\}UGz,-M(=2ONy\8 U[NC|} L`! LVN1x` 0}xڝJ@g'mcЖك(`ѴJ 1Q=z-xx|`M,ԅof 7XZ nizX1Hxe68AD`ssc\i<'1aݯG.?}GAKVb$fMKZ{2R(Zw;Ύ8mтAJ\VsdRA(IŽb]#߉DӃtq:EF?)b\d+POEE$.*^->`,wM({f7+:2=#$CLxlH հu}"Lv }3M|`!.`FK]96Bi!iR߮@(xڥ=KAgbb.DBQ +QBE*iy`BRBDF *sgw`=foٙ=A ځF mhg'fBsGh2k:X3*^sϨF)²>g$^n9J ojQԧ_sDԧϭ Qu­ N=esl"MdBl 1M#kb?Rc`!M=vxC[o3ܿC|:iָoo/}l "|"%g8#yU8[?ЋNmqvO\Ŵӟ-SZdwεJ 9)KO&N V:`l5" L$N? 鵞=i`!eATCʑ R; X@xڥK@߽DۦB+"";EqvP\Z!hmC(."]*[WI{%sy{0(`##(Ǧ̋R'x4?ip)t]]^D`+;&ρ }C.,zO K$19·y&zV7[ƺiz+={{cLUNh*+">ʝ1UɪBlIJjpYmYᗾm_aE_Zr3k/ӯQw~w`{L >DEV\H~ KΫws@4k i! Z 1UrZmNdzO@zg"?`!gS^2ל$R0, uxڥTkA3;/?("EbE [ F]bFZ+r+x&xQQ{I$EЋ@TSŮ3fl% C{o 4;@<:_6,J PZ6K㒴a=渵HvE0d8nr _{,bp4uu$y߀3'ȽHF:%|V䛶|+OT(-$0vKŹ{綁ۑoގs1՗?˪wX2A?AȥwˉNͷuC?*ufvD꾠)`w>MིAPwnJKfcVj5G*Uo2֫jأpĆy_[AւsPe#ޑ I#~IڒN:XyL<ݾ^5J̈́ hRWc!kxXjΏc!GPtbo(:CzJ?2UVͽHoz-91^7uM.nC9,D[f~Oёי*Կr9>u+` 4tp09Ur`ܑbW?DYqL(    Equation Equation.30,Microsoft Equation 3.0 Equation Equation.30,Microsoft Equation 3.0 Equation Equation.30,Microsoft Equation 3.0/Equation Equation.30,Microsoft Equation 3.04Equation Equation.30,Microsoft Equation 3.0#Equation Equation.30,Microsoft Equation 3.0'Equation Equation.30,Microsoft Equation 3.0*Equation Equation.30,Microsoft Equation 3.07Equation Equation.30,Microsoft Equation 3.0DEquation Equation.30,Microsoft Equation 3.0FEquation Equation.30,Microsoft Equation 3.0H Equation Equation.30,Microsoft Equation 3.0J!Equation Equation.30,Microsoft Equation 3.0K"Equation Equation.30,Microsoft Equation 3.0L#Equation Equation.30,Microsoft Equation 3.0M$Equation Equation.30,Microsoft Equation 3.0N%Equation Equation.30,Microsoft Equation 3.0O&Equation Equation.30,Microsoft Equation 3.0P'Equation Equation.30,Microsoft Equation 3.0Q(Equation Equation.30,Microsoft Equation 3.0R)Equation Equation.30,Microsoft Equation 3.0S*Equation Equation.30,Microsoft Equation 3.03Equation Equation.30,Microsoft Equation 3.0p4Equation Equation.30,Microsoft Equation 3.0r5Equation Equation.30,Microsoft Equation 3.0z8Equation Equation.30,Microsoft Equation 3.0~9Equation Equation.30,Microsoft Equation 3.0:Equation Equation.30,Microsoft Equation 3.0;Equation Equation.30,Microsoft Equation 3.0<Equation Equation.30,Microsoft Equation 3.0=Equation Equation.30,Microsoft Equation 3.0>Equation Equation.30,Microsoft Equation 3.0?Equation Equation.30,Microsoft Equation 3.0@Equation Equation.30,Microsoft Equation 3.0EEquation Equation.30,Microsoft Equation 3.0FEquation Equation.30,Microsoft Equation 3.0KEquation Equation.30,Microsoft Equation 3.0LEquation Equation.30,Microsoft Equation 3.0`/ 0DArialngs,0z[ 0"DWingdings,0z[ 0@ . @n?" dd@  @@`` ;$ /   /     !#$& () *+ -/51+2+3  6789 :L2$-ᘨ"CJ{2$տBNpyRdv{2$HqmsmXb2$|(LaS2$Op 投P\ 2$i(T_6^Y 2$(^Z6 (#S?z 2$a6w8Y('w>2$1OWryW2$PАʤXNQHh2$@[mr@sTZcz2$eCJ85e2$k2w_0f2$ณb^T2$r(eKi:d`2$W4Ac;COP2$4Voee:mU=2$ LVN1x!2$.`FK]96Bi!iR#2$fCG]$)%2$Xêj1'2$M=[!> J!   2Improved Method: a step back  LP proof: &    6Improved Method: a step back  & AImproved Method: a step back  & BImproved Method: apply to SDP  & CImproved Method: apply to SDP  & DImproved Method: goal GOAL: characterize graphs for which Q: Are these just graphs with girth e" k? Q GImproved Method: new SDP oDraw edge vectors close to v0 New constraint Maximize z Solve new SDP. Apply to simple cycles first. P-PP ,    o HImproved Method: results IImproved Method: pattern JImproved Method: pattern MImproved Method: pattern Suggests: Hypothesis to prove rigorously, for all graphs Tested on group of high girth graphs If true, can reuse Newman class H t ` NImproved Method: conclusion Results: Provide good hypothesis to prove/disprove Evidence that integrality gap still 2 More insight into relaxation INTUITION: edges in Ek are closely acyclic for large k CAN USE TO FORMULATE APPROXIMATION ALGORITHM. STILL (2-) m8< m   !8"N  Z  O Evaluation   Project was: Difficult: try staring at 380 X 380 matrix !! Satisfying Instructive: exposure to lots of higher material Useful: tools developed can be reused Results open new, more specific questions  * 3#3$3* PThanks to &    *Professor Charikar NEOS server My mom VZZ ZZ Z* * Q  R   /8    ` 33` Sf3f` 33g` f` www3PP` ZXdbmo` \ғ3y`Ӣ` 3f3ff` 3f3FKf` hk]wwwfܹ` ff>>\`Y{ff` R>&- {p_/̴>?" dd@,|?" dd@   " @ ` n?" dd@   @@``PR    @ ` ` p>>  (    6   `}  T Click to edit Master title style! !  0  `  RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  0P ^ `  P*   0 ^   R*   0H ^ `  R* H  0޽h ? 3380___PPT10.vL Default Design 0 zrP (    0& P    P*    0,     R*  d  c $ ?    0   0  RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  6  _P   P*    68  _    R*  H  0޽h ? 3380___PPT10.e%m |  (    Bk       <i   I     0o  A Z (Lorenzo Orecchia orecchia@ )0     0Xq   Z xFall  03 csJIW$      0t  p(  bFinal Presentation 2 H  0޽h ? 33___PPT10i.vL+D=' = @B +  0 p(   x  c $  `}   x  c $x  `   `2  s *"`Z& `2  s *"`M `2  s *"`M & `2  s *"` P `2  s *"` P & `2  s *"`q& RB  s *DZM RB  s *Dz z RB  @ s *DZM RB  s *D RB  s *D RB  s *DP RB  @ s *DP RB  s *D# # H  0޽h ? 33___PPT10i.@K+D=' = @B ++   B : @ (  x  c $P  `}   x  c $$  `   `2  s *"`Z& `2  s *"`M `2  s *"`M & `2  s *"` P `2  s *"` P & `2   s *"`q& RB   s *DZM RB   s *Dz z RB  @ s *DZM RB   s *D RB  s *D RB  s *DP RB @ s *DP RB  s *D# #   0~ S1 2   0 "z S  S2 2   0T Cz S   S3 2   00 "#  S4 2   0 C#   S5 2   0DbCC  S6 2 H  0޽h ? 33___PPT10i.@K+D=' = @B +  p..M(  x  c $;b9 b x  c $p+D=' = @B +    8Z(  8 8 c b0e0e #" 0e `}  b f 8 s *A /? ?7  / 8 0b Qmax 2 f 8 s *A 4? ?   4 8 0b~  Qmax 2  8 0b _Integer Program 2  8 0 b3  ^Linear program 2 RB  8 s *D  3   8 0bpz W  [ LP Relaxation 2  S  8 0b Y  s LP relaxation studied by Newman and Vempala (2000) Integrality Gap = 2 ; given by special high girth dense graphs,t! 25+0%  G   8 0b  {)DOES NOT IMPROVE ON TRIVIAL APPROXIMATION* 2*) H 8 0޽h ? 33___PPT10i./>+D=' = @B +    .<G(  <r < S |b `}  b  <0 TA #? ?@F  # b #<0 ZA *?AA ??  * b  <0 TA '? ?`Z  ' b &< 0b~  _Integer Program 2  '< 0Xbm )T ^Linear Program 2  (< 0b  vSemidefinite Programming 2$     +< <bR u9    -< 0z6 ) OSEMIDEFINITE PROGRAMMING: Variables are entry of semidefinite positive matrix Constraint and functions to maximize are linear combinations of these variables Each entry captures relation between two edges. 2 -201     .< 0P z' 1MORE POWER THAN LP? CAN WE PROVE INTEGRALITY GAP?2 221 H < 0޽h ? 33___PPT10i._H+D=' = @B +   ` %(  `r ` S l*z `}  z x ` c $+zqa % z   `0 ZA 7?AA ?"  7 zE8  J `Z  ` 0,z 2 eve1( 2 fB ` 6Dm66  ` 61zdt Zv0 2 `B ` 0D m6 `B ` 0D62J `B  ` 0D6 6  ` 6t7zCg  gve2*02   ` 67?)a R  @`   <d7?]a) k0,800  @`   <7?a] h10  @`   <d7?)a R  @`   <7?])a k0,750  @`  <7?]a g8  @`  <p7?) R  @`  <|7?]) gz  @`  <8?] r Cycle length     @``B  0o ?ZB  s *1 ?ZB  s *1 ?aaZB  s *1 ?ZB  s *1 ?ZB  s *1 ?3 3 ZB   s *1 ?y y `B ! 0o ?`B " 0o ?ZB # s *1 ?]]ZB $ s *1 ?))`B % 0o ?ZB . s *1 ?  6 4 0 8'D SDP solutions are approximate. Better solutions can be obtained by increasing iteration number and optimizing lambda start parameter(2 H  0޽h ? 3380___PPT10.@mG  C;)*(  x  c $en  `}  7   # #"2&          7  <n ?)y   R  @`  <n ?]y )  k0,886  @`  <n ?y ]  h18  @`  <n ?)  R  @`  <On ?] ) k0,898  @`   <n ? ] h20  @`   <n ?)3 y  R  @`   <>n ?]3 )y  k0,874  @`   <mn ?3 ]y  h16  @`   <8-?)3  R  @`  <=-?])3  k0,856  @`  <-?]3  h14  @`  <<-?) R  @`  <U-?]) k0,834  @`  <-?] h12  @`  <-?)a k0,8  @`  <-?]a) m0,800  @`  <-?a] j10  @`  <u-?)a l0,75  @`  < -?])a m0,750  @`  <w-?]a i8  @`  <d-?) o(1-2/k)  @`  <p-?]) gz  @`  <4-?] r Cycle length     @``B  0o ?ZB  s *1 ?ZB  s *1 ?aaZB  s *1 ?ZB   s *1 ?ZB ! s *1 ?3 3 ZB " s *1 ?y y `B # 0o ?`B $ 0o ?ZB % s *1 ?]]ZB & s *1 ?))`B ' 0o ?ZB ( s *1 ?  6 * 09- SDP solutions are approximate. Better solutions can be obtained by increasing iteration number and optimizing lambda start parameter(2 H  0޽h ? 3380___PPT10.@mGB   )*B(  x  c $ P `}  P L  # #"2&          P  <XP?)y   k0,889  @`  <p'P?]y )  k0,886  @`  <P?y ]  h18  @`  <P?)  i0,9  @`  <xP?] ) k0,898  @`   <P? ] h20  @`   <KP?)3 y  k0,875  @`   <0P?]3 )y  k0,874  @`   <"P?3 ]y  h16  @`   <TP?)3  k0,857  @`  <B?])3  k0,856  @`  <DB?]3  h14  @`  <B?) k0,833  @`  <?]) k0,834  @`  <dz?] h12  @`  <( ?)a i0,8  @`  <D:?]a) k0,800  @`  <x :?a] h10  @`  < :?)a j0,75  @`  <:?])a k0,750  @`  <:?]a g8  @`  <:?) o(1-2/k)  @`  <x.:?]) gz  @`  <P=:?] r Cycle length     @``B  0o ?ZB  s *1 ?ZB  s *1 ?aaZB  s *1 ?ZB   s *1 ?ZB ! s *1 ?3 3 ZB " s *1 ?y y `B # 0o ?`B $ 0o ?ZB % s *1 ?]]ZB & s *1 ?))`B ' 0o ?ZB ( s *1 ?  6 * 0o9'D SDP solutions are approximate. Better solutions can be obtained by increasing iteration number and optimizing lambda start parameter(2 H  0޽h ? 3380___PPT10.@mGV  0 V(    c `:0e0e #" 0e `}  : x  c $r:  :  0 TA ? ? .  :  09 (G(V,E) has girth e" kB(2"""  XB  0Do" "  0 TA ? ? W6  :H  0޽h ? 3380___PPT10.t,$  `$(  r  S : `}  : r  S \9 ` 9 H  0޽h ? 3380___PPT10.ғ  p(  r  S x: ` :   c H:0e0e #" 0e `}  : H  0޽h ? 3380___PPT10.q%J  J(  r  S Li  `}      <,G        0  A Lorenzo Orecchia orecchia@$ 0    @`  0  _ Fall  03 csJIW$    @`H  0޽h ? 3380___PPT10.ei]     ] (    6O: w DMathematical Programming Relaxations for the Linear Ordering ProblemEED   08: # kAdvisor: Prof. Moses Charikar   0(f  AZ vLorenzo Orecchia  @`  0  6wZ Fall  03 csJIW$    @`x  0f9@ REFERENCES: for an introduction to the linear ordering problem, LP1 and LP2 relaxations and proof of their failure in improving trivial approximation:  Approximating the Maximum Acyclic Subgraph , Alantha Newman, 2000 for an extensions to a larger class of LPs:  Fences Are Futile: On Relaxations for the Linear Ordering Problem , Alantha Newman, Santosh Vempala for an introduction to SDPs in approximation algorithms:  Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming , Michel X.Goemans, David P. Williamson  24! 2 2.CC!:o*           U         H  0޽h ? 3380___PPT10.4G  ld(    0DF8q  XREFERENCES II: for the high girth graph algorithm:  A High Girth Graph Construction , L.Sunil Chandran, SIAM J. Discrete Math. 16(3): 366-370 (2003) related problems, applicable in combination with SDP:  Approximating Minimum Feedback Sets and Multicuts in Directed Graphs , G.Even et al., 1998 D 2! 2 2 2-W     b      U 0i  0H  AZ vLorenzo Orecchia  @`  0O  6wZ Fall  03 csJIW$    @`H  0޽h ? 3380___PPT10.< 0 `((  ^  S      c $7 0    H  0޽h ? 3380___PPT10._h 0  ((   ^  S      c $= 0    H  0޽h ? 3380___PPT10._hx]h[e|߽776kg%ei9:DkZe݃f4뚙9 -TAQ|eb1"Ce ?,ޘֻNWr;|;|}+S`@g!rjl6i@lvஂP_bi|jk( [rϜ/z^;ַ߱kaSnIt &د,1ĝqŽȪfןAoGff0zpp A +FXi( 2@& w2COIotu:s (F((-ut@Tq Ȝ !"ޯ|!9`U}+f!-~a믎!tT~;~"8<1Q-9xg)n,z( =}BbqQ7~(0V?n5 +=TC/-͖cٙc|i:7 wL'ͤµ' w_SqxeAc2|`bх90zt!BAT?w CÉB'l} t:E"r0KU ~rIYZHŨikC NN!/Gгx_&`Wa'` )loSpM[(Ʃ bj˝cZ7u z5::R!^eAsallωo?\nIv?g`,IX<YOb;Q-*MAe?~3 (0=q#n]ّz~TP&.6|JdW"~](7ֲ ߏB/i9`[swV=CJIϣ.8boygxXuy Z? Y^Fl5bżvlju+#vM-GU߫E}xXk[u?77l5sn:9:D>u@&4ͺfaC e$>L'> C}Q(Q o*Ap,YVojTr~?{s77>lB/f ">5T_lRҖ{ȍvKFǠ i|Zk*Xv` 3R.,uji+WeX_=[{QMGeW` u:$ h8B?N@cqO5P׾0cv#TmW>S>)Ux] mĴE151ۥea@#q0y`B7BE'د/J;FV(PSjh^m!dNMr#ȻEB~ qeUnn<o]Px\m1qL2_A _(g|~P|~b4_Ȣ68#N /2L{}/Eo\<'-Zi :mpH|Z(jYskŞFrhoa$ "mH*%o⋚ e;U_'h"HFٓȇ0LWm$ Gr׏Na:(r()A~Φvd1ݗqL'k)Ž ndwjF#0Sv?г0" f{}\<TSz G/xu'UX)rw~B_W8yGxPy{G~ݺI`U A goa(X'm񨈮^o#?V~-[/ÃみƷuC\Qk6 _cWCݼc]beUGd^Y4\ŝ +l%_"7B^~K_\i"3^il4 G՝oo)z<[>Yq3grBy=0WÓ^(}>svԭg[ (cX&xmh[UK^;fMKe]h"ʺi KӮmB!' Ju?T*nTeK6t {ͽ{|WkYB<!x6f34aס76'!S e uҏ!޵/-8N= '`"^3'> F Y10ZW~wz0CmxJd1u ׀[ rTFKzt_6TPן?B=OgI_l0Ƨ?| =]^{w(nb">#ѤRjcѨmsZ`1@F&y,qt~ ; @Mt83yA@>l7[>F[y#\4ԎM~K3c0'.Dsm}&f_%&jOBՌzu4=.?=th ;t9X :=H ÓtjhV;惂돵?Բnꛎ,TQ>HB7ڝj>($ 2w8ؓS~Q ۫8wYCo9iJ4%Je~~Tϯ ǹZ_B+/e_Ă+sn? c\ʝki%GoTQSqb>l]IH*s_t]W 8o]p~_?k,J*1"̂()ӟ٫a|diPOO1Ěow&^8ON M$# <9 gpǼ'Z]~E˩6[ƘfY:SAܪ7hJӝ@Lxl-1I$ e38hBo;PJ])R@w@UMzt 濔nOu@s<6|Q20G`CLcW֋XWYdolj7ՀTNDo7 kj N6܅n{PU1YEn PMg7l`)92Y;GR OL} Wp3x,0Fl =?D`p&D'^ ' zkĿ1ׅk' S8^h_˔7#E 2Ɉ+y@[8uK5G56w\'ĸC],'Ө{lmX {'K/r~rmRܱ- ?v5t eDyq~GBa.]רmuڟ2ﺪ毶7Us;Ů(QYu@T]ʻEL<9Q-e L/! )˽p&JO ֢I~|EAr-2H#4php ţDxf ix9nM^dݗȳ*#BNT SPރcp(~?BSV ŜKrq[Ο73_G+CS=/͠kqG?Ut9ҿ\wqcnG[Gª֑֑iz|A=h~_ e7?)o5ea>)j]KZD}m>$^Rq~gnqN5gxn{y?o;a ~Omi$xX_hEvvn65Д4j,"=c>4JJTS5Mjrx\ T$R7,O>"Fl` Ҝ7;3n/^rovfoޥo>dAbB6 m+bt,ŚW8(>A eLuls'o䟟z>,}8t Ls'Șf{q#pq2돢~Aƴb9,}0a-u9 z Q][kNrsX>uX41ROݐj?a;ST?*ǿ'rWr N1sF|׀ؿE鈿(~Mq O+ϟ| e81 , CXM͇0_? u  SY5Dvs7+DzCh|gW7O6$ מṱ{I:C9q;oaPN`Wࣹb0[uMm)CNOޠA죱VV䍬l&Na l))lS)l6jR7$NYW٩UM;hH[%aS?V8D7OADUpkZk_y%<&COпf)m-yJɚs p ^ZE[WcC %BOZY,qtE8S&^ϡK_b5gf[΢&2%"-`gI:xx2?;24 -&_8 =8csqC%Nh sܭ.;dOqnILێ>g?w۳#a~YGy%89={GӎfwgL0Mmxq椲>"XrzԲ{ES9"oIף޵޷(t-aZso2?ۘdgǧX3ߧw|ySپne~S{]=׵U{9ĝlKFα<7j%r#lH;3_B3&gCiO9 7yy_Z`~vS>W+,_a WX‚p_g {+ hV WX𿲗CTRTj/U>?\|-$ FVb~A,|`"%l>]vYF.|X|[տIxX_HSQι3l-D3 \$$Қ4qnl.1D! 譠COBC^詈m}߹R#7ν9ۖ^-X⅐ocظJt94aU~BVe$†p-7!QIMo^~6ȧyʧ xSice[9(-?q}0}ڧPoe>oǓԉuT`Pfi/dہ`vr{=d>*]pyVe2)e!W.y v쐫0 Ћ8<KQJY}ұId})wSa#~?))c+5U@\=Nxekic0(žX$@ 5,">ScHw1)ߘgzvj]BzFBjY+Jέu0{k$|.F!Whor5։Rp“|ѰU+)gs^Tgl?gz9Ov KW)<'Ip* mo}/?_?"ϼ X|Oб ǷWvW|;osoxXOA3[5* +4D8Ũ TB(6Z,`2R)04:Xk\ԗ־_<~RO-#Vu=vƄ0)ןcRP>ٽۛ3Y8|A=D[|lΎQ#߂Wۨ)`qhMv>}?<;ckG>G ?P$+(P;ߏQd~'D Ygg 0w /p*m4|;6Bq@ߋ  5Ԟݧg$y{.Nx!h>B^uHH?j֞[@ib70YOw{ *m{oLwpȧ1!Us,(M䮡[h2B(8Mri~>v ;[e̽4Si-`$^/:rX#!!8L'Z4QƲxƒ3"Ez.B#3fɔ޾)gu 9,]^&`@ VP[.r6LRkY[]VPt yO/$TR,<gs_[-֮I~&~X+{ظ7Fϋ:`! c(m KBh /hZzBK1%C 5ݯ`tp_}tZps:g7xXALSAB[TE$$&@jjjZSP@1?bb≓!x1DAn#F/<3wVٙݝ7?mƣ'm΂*2WB%Jr4r}E."kq|r(a; RKj3dS.9Ӵd5X6__h_|oͱ(܀Di\#&[?7@+ -OI A䃲ϥx)xS+pF'N]fM9:ߤ(w *d/|~}@|B 1aP7{TU Q%.zHa4u`^a=&vĬk]pt65x69?[iI;.I'ǒO 9bs]÷ꬵZ?ao!kk+P~CelFX:SgvfY(pd8%?ә~ޜޡtyNz`|51x7,NKtIFIOj a/aggAVlHy8Qʥcp䇇[A:>q jS\jvاFLwG봝ߢo˳OxXMLQву&^mhOnHD╃&ƛFjoċM01ƃ ^uumD~ۼ73of޼7?AN|[n^lyjRl+B 4 I|V L!Yu2-#0C9(GXR?,~gGf? :ToO;sjԙQ /s. ]u7Y_7wP8\/]_IDcG͈#ٙS/Zk(9`}+UpNq#$_@y7,=dVl/821>6p$W`X)ݪ !cF 4PyLLQgL'1d[9gynkQt#bQv\84 z"0^g_< %%cp4M%"I^Ⱦz4w9(^ijP.~B!դ5NtIh:ɜşwSk90NY|׉uC>KBItL3gLKۧ%RC$U^fW[BlOUc5y=y qUz*8oQ*̈e?ZQ kkofKڣW+o}:K H:J:ڃ*xlj5*@0ӗ%b=u1EU?=J J?_>>&T+O:T>g>swNn"?t+x监QK[/k NPxXOHa7f"RBdC!4۠lfqw]݆.D'΁u Z !C]"oo\dcs{ߛf|PAX%} +F"ui(** [(>D1H/!yS,P5«F%Oo"o_(;LԔ%c;Ё3?'`1qhj}nִL6❏ABhv[7ZjI~cabI-JT[t;^wJ(-S~V_cPQP4kZnz٤×+vP54]gaI`if 2!e\PN8/Av.w7f'ϏS1:m%sղ"帅hNky>'m.Y3yl=$ i6iN#D3'YL+/n8[!2a&bi#cD4 #(FE'S'n- Y>h:Is7¿˶3O~wq}-z쀴@]v$;q?zdf_AW<ǸJ@vx߫߷rn^n7߁;;!x%uXA;3΃V:KQTnz vFd(rCf~Mq[St-D3f*i D)9?`SJ8hoIU1HxXOA3[[BH\h D 5@5?PHmhKi $xfHh7UO5FOfgZ"ۼ{>}sӁD@Z= m +mzNMrM-Eߑk'DNfO H@U0C@zn\sK^7< |}qT`Wr܁eH{U!8(iPq9XA= Y~STL$\.~4`L<_A>zY| 6"A =?~8hݕWh빵Gn՝b)>+X rrXe;N& y! ψƘoCoAt+|s,V0 wCt-L%Z#h>1:ދ3 ۧT擶LXFGCcgN}hɚh,=U-%D-e[nA\ À̹- [&%n{ L|o\pZj! |&.tŘ-RyޫE6o>yIM7;xqU!Ȝ[(,Ce|?.SAZbґO|zul=u:LV>M Y]jᄃ}\~.4dui a6"" cR9#9x~J7s6[ӥ45Y\- Ke#Q\K31&]|(hb )?+K8 NxXOHa7HM{ %Qlt5֚Uwu  :5h)ut((%F[fB-}oޛ˖wW:CNR=nc(\)5X*KC)UQQ@)!3BY0 )΂U vD;fYSt9-mT|T]! &95b0Szl:pV6P$L9& ~S T͚I x㐁G>=V֫Z@RXEf`b&A @Tj@6m-oob7Q;)?ʱ ((M(P >ڠVsE <~vYӥv}/c3 $0ZAL.$Dc< 󽢓{/CNh-!jhs=K]=&uفFch+N%F\*,H9n!Z}C58yGj)k&1!Sfo9ϵü>[/ӛv}#? G?*tR'_CL+) ]{EF[iߋ;~c2w7/d.+h',r5qyhdIt8 w Y͕Fa̯2nal:XL(%gǜ>lJ'Ͳ/*G8xHxXOA3[[BH\h D5@5K1EЖB'H]/ ͐oͫ@] jt61d@C:5i6@m:2>e0 y,l^빙Ss9-y)7];CXv=o}b&7a^vHμ?|)PyzEUs3S',:_> %{yOn4_.~}M/%+BϠ1$%ZuZpznہ.o&|u'?@wz@1 BF>szdَI^I{1:C_20M,- b] SƥG7VOsq7wbL?)-VQPSZf2%KpUEq Q~tƅšng:0 s.et k[ICcB0*ߛ30VZ5|HB!2ɥKF2]1f Tzv*' uF@eO-v6DSM5G|QoG>'2k PLѧDA -1'c>»SI=҃yLa:Q&p&hլŮA8`8 2Y]Z.,HYTNp 0e0|uM)y%yat7Mw>|Mg,J(ʙBޘTpmiƮ@|^xVlr?~Q۟?fd VxXOA3[Z*!$=H9A&0K1EwC[J MFbhic!VVԤ WPrJ4h2A\b}(+uc]ɜqNɭFOlv_7̝go3SZ&WanնIrX'q)XB=p-?)ZɜNYr䓐8^ b֭sV. nCWR  | q .Ѫ#Ђksjϝt@"([(,S|cv O1/,fh<$ao$u1EU߀_pI> o$\dg`*A*ѸpiU4Ǩ|c;Rc͞q\9F>2e7kT‹\>d^tjf_(m~{\DY ɜKP&!t7=`:;W\p&dkS'$<Bsz*ɂ6I%=]8?hɳjhE +m< @l15Y6LuODW-1l˹'<\8KP_PRZd_T*QRR%5cpf!t̫(쏠IsLA³ ڧj5m(ӲͥW!as.σ}zB4Wu?رZ"0M恨Ԗ\El*-oob?Q;)?oʱM((-(P >ڠrE<}1)z'm1Mיvi\^- [&1~}Wr'|e# %BqpJ1TuFFZv_%yͼ5\cҐ)n34h,;3aa:\qC* 3xK'c)C1 r;:/-hiزa~N#-NzZ;Eeysk=d)+fb߈'_O ݴ#3 9ƭTzrCtZο`.y-̈́.٨ I.\ Lpq2x4=bmm+}6r>h;r0kۊw#gԼΤFd~15)cp ,JqOR'K ]AxMOQpl)B B D 'PL'@J(BM!!Ɠ]#4 `pPIC{k×[$A ̼3ޛݮ|{V 6Y v3C&dr Y*NH#Lu~;q JW CtR# dL@y(aA!zyه2c,쳯EƬ swCF`)ÔCT7a++mn%d;=9~l!, P q?>Tn'iMMׅFq!JNMV( 0x dd5+j 8 PL*θVi7 u 7wvF,3o~P>H<ݯBrѤT_H*$U' Y5/<B(7z.gBy.J5Ts;ߙr:+s'V(%6IY;NS| ']J6bٸ۔y?vJY/-p$4kHɷq7叐~W:?ڐPCyjaUT'L)2_c[*HDzo"AO:]*j&cNr}';NcDFm+?O-oWx})a~bG9,.ya9z&]f ?P^ sT :cP9=9xR|h5/m3dNFᛣѱh_:2 GutX2Y,LevGxXOA3[[BH\h D 5@5?PH mhKi $xfHh7UO5FOfgZ"ۼ{>}'z:2W !jz4zZ#NZ6B2 J4?d=ˏ|ʁ*d/=<']/kv]}7rqb?ؾڦPuHgmJ-q=v@7ZYӓS ;=g D!w#B9=llj֤Aq/6=TzaQt!ngo`r?Nfd1@{Dңrͧ8F;z&b|Җ ߨh~̩-Y3vPY\帄Yl :BM7 a92]d ݤm1!IU U!l Pqgr钑LWB.YdzUF퓗t] qS-G8_2̙ T#(?51%&9_:xGqqJ1QWz0փI= ~^#d۸yU+vN8'%gBLV֡ f m#"b/9yl,9B:Lއ( د40GAJ^Onnc5]Mݽ_3ŵBT6T9S1 n9mO+OR'Ojӿ tVxXOA3B-TBH\{0@r2BM

ysON+f:7ov>0}E/!kD2;J -~=v@/򏓚YNO~N12g@1 D@D"lŊqoOQWST-AuXXE#8(!FAF-KOsqʷv=X#Qp̩S*H[&l}B%|CKV3%KsffqEq Q>yOvşk A̹ mBschLf !;ߨ>&өHl:dF@aOW+VM+YxS!(1Tߘ=>?^ #oUBj#W# /R[QH]={ ze$$q$}[90ݘ4 ۿ!lCd"xϤbi]F6;ά:/-hiش~Z#yMN-%eyCvX2g8iK$K1!'Lu uIgDŽB~x:k"wrn^Է;;o \l$uF] VNb]jS$p2Np+g4ؙ# td339#2%2ic(V~Myx??c t"ٔ)j~xMOQp,v.X!X{09yРb"H%Q)$xL 5IH?ㅃOZg]V0{;3s*>&8$.p!L@!K$IiC8PAo'aߠ"tE 0DQo.@>;$lγ k87j|G)Fcp!"iaҶ&g#a eʍga}Ro̚1x'\=Zaơ2?Dy0Du `pKn>;db/ 79Ϲ;=f3]5 00'@P5xaR7xxw}-IkBh.4 Uя{jBD=5 _d5'k'k>T3Mbs|RO}x!~e27*C1dUQtIܐZI?( r&,5OM*cxNDovŇʜ 0Jw)MR%mÔ)_ MX62e.^OPV i +y#Or(wm C#'Ώ6ĕ>o23}(_-s8?Ek-^|u|u ]EpodbM$(vZz>XE]9lYΒCky}v{o+[Ey^pfk_Jzv:+V X|zQ| {{"@ =?~8hՑWh9N:՝b)>+X?rrPe'N' z&:NƘoB@x#|=eQHx#Z;Ko4oD`܍S*H[&~Ρz >ddaKfeqco ^A̹kXB14&ө9s iUΫuKG$<Bs\d$cKjr٨hc zqSu𨍣pƗFs|Bfn!}`Lo^l޵qLRDa4w`R2Ynݯ;9V {~. {ĹdmBh:taA mD68̚r:GH3);o(Hk[m Kik:soP*,Dq%UD,.RYM zy%R=zĥVxXOA3[[*!$=H)r2BM

vkO@Ajum [ &۪ZZ#W[@h Pj 9Su8))7]3CT+cbyDNi3\EHU&8s`ɟa õ0ʧh>'sd_ǓOAbqN}rI)Ŭ[F\@܁ 8`:A@BUG^ׯn9EQR3˷)PXl(ȝ' >ļ,[h@۲SpGUe|"|ce0C7p9JoQnwDRU9\͝H}!V7{qp?<Җ [ߨP /vrВv; z}ܪY\|r\BԢOq^'϶_\ ֶ{14&ݹu!_>&өHl:ɝidF@aOS+f'M-YxC!目KV,JN!kJAY!#< y),+]Фy1E{Av) ?_BM=G Qr13m(2,T=cp I~&<^a^wUnԛQ2B:[Xea)8~~O>>ܗ}GŽZiU]_;3Pp|f!p/'`b]6֑HjPԣOYA^I?q|Qci cDzvYoĎ!λw߸1Q}[ԇ`tp͢,;58.!j}ljkB|W`QlM*g%I7јޟt<'l.gw/ko6*Bm}'ri"†yklA,v|RԚLn^3.ܼ $woK|SIA^[OxZ[ _8E{8yy5ݟL'DޗI@rq%B+ k=C'4~ج/6k|pJ3I/m7SjsIL9Qp=~`~|o>`p\OƖ)}Զϻ'b)Sy)N7Gꊈx0#qȏgiB&<9Owb@u%0ہx̡;6MfF}1m"X8oٱ.fqϽ𕫝0sS d8袭XgS;tQS[:>Ճ>j>u&Ԥ!F{jMDm8ߊaZHǷ^j~Wc _mOK:<߈2p /W#=tKw,?5""?clr yC%Wo?/o~y-_-?qxVnt[xXOQD&HhSdb5z-XꩁCG ~Co݃^Hy):۝y{3yZ6>Et$;nc 6o3*W4 q@?>Pؑ:sENd;q/ްzzL]ɦdls-tbk0fяIپ xA[i6~H<qG !I,R}L]XlLZ0>hT)n*:Yѩp3{Xǟ ?V^Zo] qHi^J(vGT(5kQLPR-Mqvoʁ1QO\k!HOSWG4!.d~=pQg\)9#"/ҋs)1lJm0l/@Oǰ !l$W|#_'McBW[9Uqha2T(J ᮘLg_XKۊl0\ 3DNIVD甑x2>R`*)C^cFg]ӏ~-7UŸ*^⇊J4H cbuN=8Aui}<'ߐ&1{3}{MAy Cs0L̆ ~qU4=L}vVV'q6Іg< %@(ƣ?:nHj=踝%y5$ &cĐ_ꏒ/ϟzuRusI׳z>o킗dep>p-/=~unג& Z@\K Z?i君DM[jPApʴi/#X?q,[k[ߎ*;툩U6Up_F"txXMhQ^6ۘQh5i@TOJJ1ZPăx"z X"zE UӃO{om"U3a;73o ?,pe3ȒM `"P6d$P3yK !hHgSR,|CI yIN,NVL{Y[qqhP K4v27P;$:I3q)MkWI*lkm^ _pa ? u1(o3_ՕAr,KCr*9i6\良.ӵ`}Eb^C&nj~,1ͭz/Z.䨚-ֶ{+\>XT 8zPCs<)ٲ;ݎtDGV{%Sp?h>(OgB<>9AMRu( |{P>x"^dk|+EbF+m W8P@"fDr˾pC^/y!ݙAvpY=TnJYqq07w,r2ټJV/eyo7u?W@Px)_؍Y9zS[' s%3Yc 0Ň6_w6_~S X3J(!|Ʈ"l\ ol~Xhoj)Ÿ3S))va deb5[K]H1$tƟcaFCL\@ܸ4&53s4HBjzәo^眹q7[2: E'ԗ1dn7@1V(4$5*\8h%jt`4 e@?ı]\y*#ub(=ΞuvRM,??*D^M/]|{L֔:5CR-ҀJoCnS8$1ъ{P>@ӊ/?u/xxV#Wb;|Yhaİi{%cvka/1;=^^.'ߧR0| Eq∠9dqQ듳NnT_=6ƚu.%[Ǩ y=F1D1\2LoES߹L΁׆f_.H,>9G󯲀oL&eŰvT% /[!G-DJ>zqop~FHNNu.7΍3ehԿWێW}ℇ,|RZ6^\=$!{ oRaKa'q޴Oz7IoJ7O2νSt&#Q)<-3;SL.Sۈawe]7H'f3?Dq}7"Kɹ)kL |că6U5ڍ~M*xXKhTIU/ߗN:I|f0?ӂ $"ơ%ݱtFDf1d!.…`ìFE.43[ުze[F}јطWu[q}r(ɫc\]rT`dJI Ѕ.)|T؜9?,dX^;CY}; 61hlm/HZL5ן8m nι^f" .qE|tNU.6թE{'Zn_ɷ?vJ]x4k;Wz߂*?29=5!t-/Tϧ;*La0TktBZ\گ:V+cȁ(8aXw0>"1O``Y=5Xgƥjfީngsd/}c} eEږ ߨG0OዓCKvfʷd/(J%Ʊ Yjbu] E#d?a X:w/1-b'^#ҧ^q2w **05*![Er[jdVcŐQjf&o {P}29(,5~1F!++X~BU>kpI)k7r+^1-dkeT F_s*ӌ%g2QoN"qA^{i{Ҽyh #j=fcc]mOS]ҦE2jꤳi)X~yoME GV3AŢܟ6[ 4ͫt $6A?z aaaaa1bc[xWOSA-})S$@ kJSb m)-z"cH?c6 x4ufw߳4HB0fۯ7{ۺyA3 XrC}CbT!\сVFF_LByW?R'f):\甪t7T(k덫^fԩ1aժmUkr;XG̡SZS j=ӺϵxQ9nm kXuoߪ Aj_ B 8HbitQT95 n%d;=9J˔wX&dr3!rO\qW>?w/*rVbc|[ haİ{E=NhըƝ>@/bS)si_&l}@A8*h=YaTz,y[=U-#d/X7E--N/|.'R;O<sfoz r ?ңqC{!M^(ݼ2O<8O3h\LK}~=WygйХ/ w]76ʤf0RIs$0$KɅI{L#ô6U5ډ~ xXMHTQ>9::$"r *3B MTEgtͱ20"ZAm#jBP,iW&hah!3s}7-ޘ {νιy4א@{X< җ2A@8 &-!6ډM0j0"`=#G_O9s甒ޔSmOd6O=dTSҤ!nk2d_\ }/ڧh>'c Taj9O.okqLI/`3?yЇ@B'e|>q{ͩZToS@2vgn\dO:BnCe9}k1~)}14wA6z艛\5Ww"| e>>a=4 4p9?_r#Arvi3I>2e7U ;xA0_K힬⋖WJ,[yk."~{JUͥL 1HwH?s"q9L]-*z{!?Լ$SC^HX(rg[Q9'v/ xILZA֗֗cQjfqz'Wq >p}jGpV_^-c1fvv5>Iا4A/4n/k)?w1)A3Wy܏yrQԘ+"h6E 7剺0)q^>2 .eLBhԲjr0U'|{lKs`+b:#pU_S+Jفv-jzYa_bH?CxMo[Epvى?ƍ*%FJh*'@ #q!jQ8!ADAOXEJ@R9p@-_خ=G O4μy3r`{ u<-"мJZ%@v`GvсmSiz'1 }zFIvZVވg.yrz?C;?}ޘԛ2\onkWlVNoi~QӝFCs{}]݈~@@g^G~ogl/zYC@/ʵ`L& ]g .M =J_`?_7.0 IUa%*_r dwGQ74(A$i/D]iGduV;߈:e;To4 "$H_>Npkn򋘣 f} uN?vSTէ`Kp#_;]8ͨ'Jt܇ó,.~T.-%ngZzƇN"޲-{m]qfgФ_,df0.Q@ ~(ބM.㍘yTػ3ﷶ'uv_"C=/u> _\O0d* O$ ST< Agٸ F5{ŭ{$}GļTMFFWUt-;K_-r= 9h[^ix7Cj[{5Od鈡j^IZcS6sCQWQgA&>KZџ'\nwu"y\&·cs|2W&k {{[pvA7D '{C&;&i]+9滿{νӟ~l} Cv|x XBTe|>ok "0ߣq¢u 2YYP[~ xmzF Z֘bg46WMVߋOA=~xͻmwH}Z Q^^<~tN=2߀in ɩ}PEV_j{ދ5|%cp cx)4+e;n]rƯ:W:L |c [7l&՗_>3wD`0M:#st&? ƧBd T~~>LM ,;Ƅl P36 lξ2l3ǟ\սV|jPZqQԒ7p;'_Q1]\[xA Y}]w 1C2G:>ud߭k}>S'#]Cp 8,d^j;ބdO&n^5 (=#y.2dlA/_Z_ O M5HxZc:—5we<w [}Ѵ՟L Bq[c㮟z4 zk|C8>rV~ydj\s0ɜbq?)z8 &c[^-_1~ ;5b47e܃Z <<OELx^3G:I;Ȁts8{tKGC)+2vl(KZ;zzS.jSC_Zkhæ+v;~e-o[\2_duܟ ?4p!ҼJc^ -&Co6;K}6xNN$Y_&xKoIޱT1Q2 ӽD%&,M\d yi>EЭ5@W4V*jlv4f@chU|Վ.P|@kxXOQ^ti?.=@@O&jScm)K=!'^1F &ţ!Ĩu潷kml0μffw~ovM>@+2?@+e +\Z 6hh˂ !Hy[?i39SrhjTSoU(+m{>>dOiPc NMpVkm`?'aDziE>e?w>0(iU5"l7ob7MA/ SE)Z&VpzNvީZzoimg =ًCބ@ ^Q%;ѧ) Ƅa0^ 8><'  ̅@0hfՌR`nZ,A C83XE@+st-n}>C!-VΨuɫTnI/ZN˓4fEGKH(D 1dㅓxފS߹:~nۼ$Q?LIYސ8Gؤt2Gr;ۃZI_{y陵Ji[i =d.Az֟H,,.Kv\ED5jS)JXo7ge~I2]Ņ#XYMo!Hm CW!MP> T'<8ƒפ1n@\=<O(Ils {ÕJeahUwdDz2}6k2Sl<2 Vrl`e߃Le49K&pi,]̚7.%M:?q= ~>j,'0mk:teavMP%!xXMhSAMc65*" j `ſҊJ/5I1@ A<AЃDKUÁ2{ n378$g^ҞmIfJ 2^絭d$FȂpX ӣm$u+ H@+RlHvfa/{L:gkO7ё;ړN"n/jhluiꂆEa|Bm59㸘%p_A*VE 78c#Oň7F.xXOHA3su?HA²:d^-VuXb !'sJTœԋs*Wwe`mڵ8q.Xݤ0Љ8<ЪЈЃS9Nj%md7=9lPGv#oA.@.q"P 2R>mԃKe(Y"ci2Y? Co{@a| g'jg5\Mc7>[S7S 83 H96qO#Y/!o@ГbNo%OvKVqqBXrn{+ B\8 7CF ɸpg}霈\Z&uoV1fh?xBJNPi B ;z|ill;z:h1[[\5~ISw?-/G-/J!Zm!|[_iC5^H/pp`j Ĭcpg,_.o=Gitx%M.A[@u[խusw?5݂!{B_y&ϧ!dqR|!ل5|j4 Gf<ފV2UD"ZuQ8eF0!v9!LP}`6~&,O[aHJg*}q8xr02Zh0g`u˞_Kn5 w'axXKlIIp2Y+"%'$iD9Ab|L9EE Nr@|ڵmNpHYi1U=qeU5SUz~՛^B Ͱ*a&UR6. KN5EG $8c.vwNKs'w]LTS˒O:po5Xր)ce|YeX0>0C@:eCIא&۴C[RŅM cN?.9R+ſ70O߂I㟤Rmg_p]dS)7Uo y ̜P? (AA@&lEQ;U"Ie&BiyS^ O9r@+6WΧ:V=({#2;Λt:u&o:ZVϵ|gT?g~>ۇ+}~ 8dUOGYe;("4CO.0:6Qfn)J-q eT_5_h!yϫ`:s)2!rYCspp0yhz$Lb=+@k8v7ڱ򐞋|rIμ(yޣXx#`:ͥ6c12SAɄmyM+O%.Xd#AoЈZBr$-1E=okFvBv}7Τ}QSB~Jeݜn),ۺ^^; %NAj7vl۳7 =z,9뛉m[|hTW on^ dp891,k\i,&ӻqkԎta:o]N*WTMG|oFD_'&Q3/oOһ{9v(4* ju yZ owL%IJΟ᳁oNpm|U>najqBu÷d]_> ?[-OO@=Ggo?u3#wxD?bpxxXQhWM&MDiI$MD?$njG1lpnb֬$~ _)] ,?%B)Y}dvYg2Keev}3wwν}k?9!cظRt9V(hHVKM '!s`BtA ˾هO&0ը0u &!˦[t폗9[uOcRG>ŀ¾9&dK_>3-oaЏݧyo\ߚlM8;J5 U)WFo^`OVeN㿨yW7'e}7Cqp `E0 a #?q<0,YOQil>A6cRt@923U)/ϧMqO9#lm bnT^\dP=XwZ.h}kiδ&хYDBJX{|}=х8>;z@=M*13f7/75vnwfzv㸄 n9qk bw`d {?pL ˝=iNa:.l g(4ph?L'fD8Merlu?XɿϘS{h1ևA>G79Hk/)̗}&8^hYSOlOv@a)֍;<}Г}%S >Fxvƛt u7fͿ~2(_mCŃ.Ѩ I,\ pW`q3bit1k߭Fr Wrat%~M9N\21D)bwYVy`.-l?S|i'9`-7E=GenVFFo 2`Ku}sO/[fZb)M6/Wz[',|c9q~sSD^<~wq9Y xXKOSA>3.RBb@@\ И)B[$H Wƭ cH$*qaԅW(zK)Uf:ܙ9y5W6^Hrv1,6]-b1ҰIJB z!UAI7Ԑi9|,ٻM O1ҩ\CN@x3t,^+s*T?G7ߎ oeN9J0.N9IOd-ŽeU?mgiR:Tj# !ORmeNU̳:/O'U7.~ P A6or -߇vD?ЮЈ%t>hR?7rzk!)?3?gݓ(R e@>PίPu6gR^'lN ukQ)(]&lQPA8p]1d%W#FI ђQZvB">Q *%Lc!4z<]~/eEdS?&׮S[KE>l]w8:BODvcqLfrM&j֯j%47*9~Oƣ&MXpJb9cy}D!I\dR&bj<&3q='\oBZV^NK֓?:PDZN>iMsm-`] 6+%9`]h$6]0Νѡ7@H=pENd#1??Шo>;9[yD^ ʁO(OVD&e3ϩ\9OouصWJma(f~ ѭWee)(~9a#۷T)]PxS}>nyT[@z3`+PmqMh;Yw?}9㡱X0&,gQ?D[|C *||j{ YprqA 1<Ay>G8ulE2Z bv9m$ B-ZٹCo\ qc4DPg|KH4bUQks,_ycf=I38LqS/K a9('Jw3N7BhǞ;=yLxGyT#ss|]̤`,ܵpMZ}K=‰j52ތf&trްeHtWʉU|jRњQ9a,mFBݱ`4Af8_K*)Ew:4GJzVD|VI/}^E)mQs"e.bQ8Ttm#zWjy>6d@FV>WѭVze֫ʬ?_9"mgYn,ߦX1%E{[DV|Jd8}6j{hWu' eWEnk^lC1P=d͕)z\Uqғ;MLz.BW 8t?}hWނϝޙP'O%G}Xt4L˫S=9yXD}g+] ǯ8QUa U0]m.Xgz9^?%V{5#v︷Xh/Jr<yL]\[Vaiu(ĦI~fpզ׺}9LBKM( 8_Z  E>!A\ C%z)ra#@^- 2|[-? a7R qL(    Equation Equation.30,Microsoft Equation 3.0 EquatiOn-screen Show Casaree/G A $Arial WingdingsDefault DesignMicrosoft Equation 3.0EMathematical Programming Relaxations for the Linear Ordering ProblemReview of the problemReview of the problemReview of the problem"Overview: approximation algorithmLP RelaxationLP RelaxationSDP relaxationSDP relaxation: how it worksSDP relaxation: how it worksSDP relaxation: how it worksSDP relaxation: how it worksSDP relaxation: lucky caseGoal: assess the SDPMethod: some toolsMethod: testing the SDPImproved Method: a step backImproved Method: a step backImproved Method: a step backImproved Method: apply to SDPImproved Method: apply to SDPImproved Method: goalImproved Method: new SDPImproved Method: resultsImproved Method: patternImproved Method: patternImproved Method: patternImproved Method: conclusion Evaluation Thanks to Slide 31 Slide 32  Fonts UsedDesign TemplateEmbedded OLE Servers Slide Titles . 32 _ LorenzoLorenzo  % ! .-@Arial-. 2 O(Lorenzo Orecchia    .-@Arial-. 2 'orecchia  .-@Arial-.  2 @(.-@Arial-. 2 O Fall 03   .-@Arial-. 2 OPcsJIWh %.-@Arial-. "2 hFinal Presentation    .-՜.+,0t    On-screen Show Casaree/G A $Arial WingdingsDefault DesignMicrosoft Equation 3.0EMathematical Programming Relaxations for the Linear Ordering ProblemReview of the problemReview of the problemReview of the problem"Overview: approximation algorithmLP RelaxationLP RelaxationSDP relaxationSDP relaxation: how it worksSDP relaxation: how it worksSDP relaxation: how it worksSDP relaxation: how it worksSDP relaxation: lucky caseGoal: assess the SDPMethod: some toolsMethod: testing the SDPImproved Method: a step backImproved Method: a step backImproved Method: a step backImproved Method: apply to SDPImproved Method: apply to SDPImproved Method: goalImproved Method: new SDPImproved Method: resultsImproved Method: patternImproved Method: patternImproved Method: patternImproved Method: conclusion Evaluation Thanks to Slide 31 Slide 32  Fonts UsedDesign TemplateEmbedded OLE Servers Slide Titles _8LorenzoLorenzo  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./01234R67QSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Root EntrydO)0h@Pictures/Current User<5SummaryInformation(, PowerPoint Document(/DocumentSummaryInformation8%on Equation.30,Microsoft Equation 3.0 Equation Equation.30,Microsoft Equation 3.0/Equation Equation.30,Microsoft Equation 3.04Equation Equation.30,Microsoft Equation 3.0#Equation Equation.30,Microsoft Equation 3.0'Equation Equation.30,Microsoft Equation 3.0*Equation Equation.30,Microsoft Equation 3.07Equation Equation.30,Microsoft Equation 3.0DEquation Equation.30,Microsoft Equation 3.0FEquation Equation.30,Microsoft Equation 3.0H Equation Equation.30,Microsoft Equation 3.0J!Equation Equation.30,Microsoft Equation 3.0K"Equation Equation.30,Microsoft Equation 3.0L#Equation Equation.30,Microsoft Equation 3.0M$Equation Equation.30,Microsoft Equation 3.0N%Equation Equation.30,Microsoft Equation 3.0O&Equation Equation.30,Microsoft Equation 3.0P'Equation Equation.30,Microsoft Equation 3.0Q(Equation Equation.30,Microsoft Equation 3.0R)Equation Equation.30,Microsoft Equation 3.0S*Equation Equation.30,Microsoft Equation 3.03Equation Equation.30,Microsoft Equation 3.0p4Equation Equation.30,Microsoft Equation 3.0r5Equation Equation.30,Microsoft Equation 3.0z8Equation Equation.30,Microsoft Equation 3.0~9Equation Equation.30,Microsoft Equation 3.0:Equation Equation.30,Microsoft Equation 3.0;Equation Equation.30,Microsoft Equation 3.0<Equation Equation.30,Microsoft Equation 3.0=Equation Equation.30,Microsoft Equation 3.0>Equation Equation.30,Microsoft Equation 3.0?Equation Equation.30,Microsoft Equation 3.0@Equation Equation.30,Microsoft Equation 3.0EEquation Equation.30,Microsoft Equation 3.0FEquation Equation.30,Microsoft Equation 3.0KEquation Equation.30,Microsoft Equation 3.0LEquation Equation.30,Microsoft Equation 3.0`/ 0DArialngs,0z[ 0"DWingdings,0z[ 0@ . @n?" dd@  @@`` ;$ /   /     !#$& () *+ -/51+2+3  6789 :L2$-ᘨ"CJ{2$տBNpyRdv{2$HqmsmXb2$|(LaS2$Op 投P\ 2$i(T_6^Y 2$(^Z6 (#S?z 2$a6w8Y('w>2$1OWryW2$PАʤXNQHh2$@[mr@sTZcz2$eCJ85e2$k2w_0f2$ณb^T2$r(eKi:d`2$W4Ac;COP2$4Voee:mU=2$ LVN1x!2$.`FK]96Bi!iR#2$fCG]$)%2$Xêj1'2$M=[!> J!   2Improved Method: a step back  LP proof: &    6Improved Method: a step back  & AImproved Method: a step back  & BImproved Method: apply to SDP  & CImproved Method: apply to SDP  & DImproved Method: goal GOAL: characterize graphs for which Q: Are these just graphs with girth e" k? Q GImproved Method: new SDP oDraw edge vectors close to v0 New constraint Maximize z Solve new SDP. Apply to simple cycles first. P-PP ,    o HImproved Method: results IImproved Method: pattern JImproved Method: pattern MImproved Method: pattern Suggests: Hypothesis to prove rigorously, for all graphs Tested on group of high girth graphs If true, can reuse Newman class H t ` NImproved Method: conclusion Results: Provide good hypothesis to prove/disprove Evidence that integrality gap still 2 More insight into relaxation INTUITION: edges in Ek are closely acyclic for large k CAN USE TO FORMULATE APPROXIMATION ALGORITHM. STILL (2-) m8< m   !8"N  Z  O Evaluation   Project was: Difficult: try staring at 380 X 380 matrix !! Satisfying Instructive: exposure to lots of higher material Useful: tools developed can be reused Results open new, more specific questions  * 3#3$3* PThanks to &    *Professor Charikar NEOS server My mom VZZ ZZ Z* * Q  R   /8  xX_h[Uιifiz1^ڒm N3UY|Fƒ.Mf͢jc {APATqZ{ė sksir7eЙ/;sn>目KV,JN!kJAY!#< y),+]Фy1E{Av) ?_BM=G Qr13m(2,T=cp I~&<^a^wUnԛQ2B:[Xea)8~~O>>ܗ}GŽZiU]_;3Pp|f!p/'`b]6֑HjPԣOYA^I?q|Qci cDzvYoĎ!λw߸1Q}[ԇ`tp͢,;58.!j}ljkB|W`QlM*g%I7јޟt<'l.gw/ko6*Bm}'ri"†yklA,v|RԚLn^3.ܼ $woK|SIA^[OxZ[ _8E{8yy5ݟL'DޗI@rq%B+ k=C'4~ج/6k|pJ3I/m7SjsIL9Qp=~`~|o>`p\OƖ)}Զϻ'b)Sy)N7Gꊈx0#qȏgiB&<9Owb@u%0ہx̡;6MfF}1m"X8oٱ.fqϽ𕫝0sS d8袭XgS;tQS[:>Ճ>j>u&Ԥ!F{jMDm8ߊaZHǷ^j~Wc _mOK:<߈2p /W#=tKw,?5""?clr yC%Wo?/o~y-_-?qxVnt[xXOQD&HhSdb5z-XꩁCG ~Co݃^Hy):۝y{3yZ6>Et$;nc 6o3*W4 q@?>Pؑ:sENd;q/ްzzL]ɦdls-tbk0fяIپ xA[i6~H<qG !I,R}L]XlLZ0>hT)n*:Yѩp3{Xǟ ?V^Zo] qHi^J(vGT(5kQLPR-Mqvoʁ1QO\k!HOSWG4!.d~=pQg\)9#"/ҋs)1lJm0l/@Oǰ !l$W|#_'McBW[9Uqha2T(J ᮘLg_XKۊl0\ 3DNIVD甑x2>R`*)C^cFg]ӏ~-7UŸ*^⇊J4H cbuN=8Aui}<'ߐ&1{3}{MAy Cs0L̆ ~qU4=L}vVV'q6Іg< %@(ƣ?:nHj=踝%y5$ &cĐ_ꏒ/ϟzuRusI׳z>o킗dep>p-/=~unג& Z@\K Z?i君DM[jPApʴi/#X?q,[k[ߎ*;툩U6Up_F"txXMhQ^6ۘQh5i@TOJJ1ZPăx"z X"zE UӃO{om"U3a;73o ?,pe3ȒM `"P6d$P3yK !hHgSR,|CI yIN,NVL{Y[qqhP K4v27P;$:I3q)MkWI*lkm^ _pa ? u1(o3_ՕAr,KCr*9i6\良.ӵ`}Eb^C&nj~,1ͭz/Z.䨚-ֶ{+\>XT 8zPCs<)ٲ;ݎtDGV{%Sp?h>(OgB<>9AMRu( |{P>x"^dk|+EbF+m W8P@"fDr˾pC^/y!ݙAvpY=TnJYqq07w,r2ټJV/eyo7u?W@Px)_؍Y9zS[' s%3Yc 0Ň6_w6_~S X3J(!|Ʈ"l\ ol~Xhoj)Ÿ3S))va deb5[K]H1$tƟcaFCL\@ܸ4&53s4HBjzәo^眹q7[2: E'ԗ1dn7@1V(4$5*\8h%jt`4 e@?ı]\y*#ub(=ΞuvRM,??*D^M/]|{L֔:5CR-ҀJoCnS8$1ъ{P>@ӊ/?u/xxV#Wb;|Yhaİi{%cvka/1;=^^.'ߧR0| Eq∠9dqQ듳NnT_=6ƚu.%[Ǩ y=F1D1\2LoES߹L΁׆f_.H,>9G󯲀oL&eŰvT% /[!G-DJ>zqop~FHNNu.7΍3ehԿWێW}ℇ,|RZ6^\=$!{ oRaKa'q޴Oz7IoJ7O2νSt&#Q)<-3;SL.Sۈawe]7H'f3?Dq}7"Kɹ)kL |că6U5ڍ~M*xXKhTIU/ߗN:I|f0?ӂ $"ơ%ݱtFDf1d!.…`ìFE.43[ުze[F}јطWu[q}r(ɫc\]rT`dJI Ѕ.)|T؜9?,dX^;CY}; 61hlm/HZL5ן8m5 nι^f" .qE|tNU.6թE{'Zn_ɷ?vJ]x4k;Wz߂*?29=5!t-/Tϧ;*La0TktBZ\گ:V+cȁ(8aXw0>"1O``Y=5Xgƥjfީngsd/}c} eEږ ߨG0OዓCKvfʷd/(J%Ʊ Yjbu] E#d?a X:w/1-b'^#ҧ^q2w **05*![Er[jdVcŐQjf&o {P}29(,5~1F!++X~BU>kpI)k7r+^1-dkeT F_s*ӌ%g2QoN"qA^{i{Ҽyh #j=fcc]mOS]ҦE2jꤳi)X~yoME GV3AŢܟ6[ 4ͫt $6A?z aaaaa1bc[xWOSA-})S$@ kJSb m)-z"cH?c6 x4ufw߳4HB0fۯ7{ۺyA3 XrC}CbT!\сVFF_LByW?R'f):\甪t7T(k덫^fԩ1aժmUkr;XG̡SZS j=ӺϵxQ9nm kXuoߪ Aj_ B 8HbitQT95 n%d;=9J˔wX&dr3!rO\qW>?w/*rVbc|[ haİ{E=NhըƝ>@/bS)si_&l}@A8*h=YaTz,y[=U-#d/X7E--N/|.'R;O<sfoz r ?ңqC{!M^(ݼ2O<8O3h\LK}~=WygйХ/ w]76ʤf0RIs$0$KɅI{L#ô6U5ډ~ xXMHTQ>9::$"r *3B MTEgtͱ20"ZAm#jBP,iW&hah!3s}7-ޘ {νιy4א@{X< җ2A@8 &-!6ډM0j0"`=#G_O9s甒ޔSmOd6O=dTSҤ!nk2d_\ }/ڧh>'c Taj9O.okqLI/`3?yЇ@B'e|>q{ͩZToS@2vgn\dO:BnCe9}k1~)}14wA6z艛\5Ww"| e>>a=4 4p9?_r#Arvi3I>2e7U ;xA0_K힬⋖WJ,[yk."~{JUͥL 1HwH?s"q9L]-*z{!?Լ$SC^HX(rg[Q9'v/ xILZA֗֗cQjfqz'Wq >p}jGpV_^-c1fvv5>Iا4A/4n/k)?w1)A3Wy܏yrQԘ+"h6E 7剺0)q^>2 .eLBhԲjr0U'|{lKs`+b:#pU_S+Jفv-jzYa_bH?CxMo[Epvى?ƍ*%FJh*'@ #q!jQ8!ADAOXEJ@R9p@-_خ=G O4μy3r`{ u<-"мJZ%@v`GvсmSiz'1 }zFIvZVވg.yrz?C;?}ޘԛ2\onkWlVNoi~QӝFCs{}]݈~@@g^G~ogl/zYC@/ʵ`L& ]g .M =J_`?_7.0 IUa%*_r dwGQ74(A$i/D]iGduV;߈:e;To4 "$H_>Npkn򋘣 f} uN?vSTէ`Kp#_;]8ͨ'Jt܇ó,.~T.-%ngZzƇN"޲-{m]qfgФ_,df0.Q@ ~(ބM.㍘yTػ3ﷶ'uv_"C=/u> _\O0d* O$ ST< Agٸ F5{ŭ{$}GļTMFFWUt-;K_-r= 9h[^ix7Cj[{5Od鈡j^IZcS6sCQWQgA&>KZџ'\nwu"y\&·cs|2W&k {{[pvA7D '{C&;&i]+9滿{νӟ~l} Cv|x XBTe|>ok "0ߣq¢u 2YYP[~ xmzF Z֘bg46WMVߋOA=~xͻmwH}Z Q^^<~tN=2߀in ɩ}PEV_j{ދ5|%cp cx)4+e;n]rƯ:W:L |c [7l&՗_>3wD`0M:#st&? ƧBd T~~>LM ,;Ƅl P36 lξ2l3ǟ\սV|jPZqQԒ7p;'_Q1]\[xA Y}]w 1C2G:>ud߭k}>S'#]Cp 8,d^j;ބdO&n^5 (=#y.2dlA/_Z_ O M5HxZc:—5we<w [}Ѵ՟L Bq[c㮟z4 zk|C8>rV~ydj\s0ɜbq?)z8 &c[^-_1~ ;5b47e܃Z <<OELx^3G:I;Ȁts8{tKGC)+2vl(KZ;zzS.jSC_Zkhæ+v;~e-o[\2_duܟ ?4p!ҼJc^ -&Co6;K}6xNN$Y_&xKoIޱT1Q2 ӽD%&,M\d yi>EЭ5@W4V*jlv4f@chU|Վ.P|@kxXOQ^ti?.=@@O&jScm)K=!'^1F &ţ!Ĩu潷kml0μffw~ovM>@+2?@+e +\Z 6hh˂ !Hy[?i39SrhjTSoU(+m{>>dOiPc NMpVkm`?'aDziE>e?w>0(iU5"l7ob7MA/ SE)Z&VpzNvީZzoimg =ًCބ@ ^Q%;ѧ) Ƅa0^ 8><'  ̅@0hfՌR`nZ,A C83XE@+st-n}>C!-VΨuɫTnI/ZN˓4fEGKH(D 1dㅓxފS߹:~nۼ$Q?LIYސ8Gؤt2Gr;ۃZI_{y陵Ji[i =d.Az֟H,,.Kv\ED5jS)JXo7ge~I2]Ņ#XYMo!Hm CW!MP> T'<8ƒפ1n@\=<O(Ils {ÕJeahUwdDz2}6k2Sl<2 Vrl`e߃Le49K&pi,]̚7.%M:?q= ~>j,'0mk:teavMP%!xXMhSAMc65*" j `ſҊJ/5I1@ A<AЃDKUÁ2{ n378$g^ҞmIfJ 2^絭d$FȂpX ӣm$u+ H@+RlHvfa/{L:gkO7ё;ړN"n/jhluiꂆEa|Bm59㸘%p_A*VE 78c#Oň7F.xXOHA3su?HA²:d^-VuXb !'sJTœԋs*Wwe`mڵ8q.Xݤ0Љ8<ЪЈЃS9Nj%md7=9lPGv#oA.@.q"P 2R>mԃKe(Y"ci2Y? Co{@a| g'jg5\Mc7>[S7S 83 H96qO#Y/!o@ГbNo%OvKVqqBXrn{+ B\8 7CF ɸpg}霈\Z&uoV1fh?xBJNPi B ;z|ill;z:h1[[\5~ISw?-/G-/J!Zm!|[_iC5^H/pp`j Ĭcpg,_.o=Gitx%M.A[@u[խusw?5݂!{B_y&ϧ!dqR|!ل5|j4 Gf<ފV2UD"ZuQ8eF0!v9!LP}`6~&,O[aHJg*}q8xr02Zh0g`u˞_Kn5 w'axXKlIIp2Y+"%'$iD9Ab|L9EE Nr@|ڵmNpHYi1U=qeU5SUz~՛^B Ͱ*a&UR6. KN5EG $8c.vwNKs'w]LTS˒O:po5Xր)ce|YeX0>0C@:eCIא&۴C[RŅM cN?.9R+ſ70O߂I㟤Rmg_p]dS)7Uo y ̜P? (AA@&lEQ;U"Ie&BiyS^ O9r@+6WΧ:V=({#2;Λt:u&o:ZVϵ|gT?g~>ۇ+}~ 8dUOGYe;("4CO.0:6Qfn)J-q eT_5_h!yϫ`:s)2!rYCspp0yhz$Lb=+@k8v7ڱ򐞋|rIμ(yޣXx#`:ͥ6c12SAɄmyM+O%.Xd#AoЈZBr$-1E=okFvBv}7Τ}QSB~Jeݜn),ۺ^^; %NAj7vl۳7 =z,9뛉m[|hTW on^ dp891,k\i,&ӻqkԎta:o]N*WTMG|oFD_'&Q3/oOһ{9v(4* ju yZ owL%IJΟ᳁oNpm|U>najqBu÷d]_> ?[-OO@=Ggo?u3#wxD?bpxxXQhWM&MDiI$MD?$njG1lpnb֬$~ _)] ,?%B)Y}dvYg2Keev}3wwν}k?9!cظRt9V(hHVKM '!s`BtA ˾هO&0ը0u &!˦[t폗9[uOcRG>ŀ¾9&dK_>3-oaЏݧyo\ߚlM8;J5 U)WFo^`OVeN㿨yW7'e}7Cqp `E0 a #?q<0,YOQil>A6cRt@923U)/ϧMqO9#lm bnT^\dP=XwZ.h}kiδ&хYDBJX{|}=х8>;z@=M*13f7/75vnwfzv㸄 n9qk bw`d {?pL ˝=iNa:.l g(4ph?L'fD8Merlu?XɿϘS{h1ևA>G79Hk/)̗}&8^hYSOlOv@a)֍;<}Г}%S >Fxvƛt u7fͿ~2(_mCŃ.Ѩ I,\ pW`q3bit1k߭Fr Wrat%~M9N\21D)bwYVy`.-l?S|i'9`-7E=GenVFFo 2`Ku}sO/[fZb)M6/Wz[',|c9q~sSD^<~wq9Y xXKOSA>3.RBb@@\ И)B[$H Wƭ cH$*qaԅW(zK)Uf:ܙ9y5W6^Hrv1,6]-b1ҰIJB z!UAI7Ԑi9|,ٻM O1ҩ\CN@x3t,^+s*T?G7ߎ oeN9J0.N9IOd-ŽeU?mgiR:Tj# !ORmeNU̳:/O'U7.~ P A6or -߇vD?ЮЈ%t>hR?7rzk!)?3?gݓ(R e@>PίPu6gR^'lN ukQ)(]&lQPA8p]1d%W#FI ђQZvB">Q *%Lc!4z<]~/eEdS?&׮S[KE>l]w8:BODvcqLfrM&j֯j%47*9~Oƣ&MXpJb9cy}D!I\dR&bj<&3q='\oBZV^NK֓?:PDZN>iMsm-`] 6+%9`]h$6]0Νѡ7@H=pENd#1??Шo>;9[yD^ ʁO(OVD&e3ϩ\9OouصWJma(f~ ѭWee)(~9a#۷T)]PxS}>nyT[@z3`+PmqMh;Yw?}9㡱X0&,gQ?D[|C *||j{ YprqA 1<Ay>G8ulE2Z bv9m$ B-ZٹCo\ qc4DPg|KH4bUQks,_ycf=I38LqS/K a9('Jw3N7BhǞ;=yLxGyT#ss|]̤`,ܵpMZ}K=‰j52ތf&trްeHtWʉU|jRњQ9a,mFBݱ`4Af8_K*)Ew:4GJzVD|VI/}^E)mQs"e.bQ8Ttm#zWjy>6d@FV>WѭVze֫ʬ?_9"mgYn,ߦX1%E{[DV|Jd8}6j{hWu' eWEnk^lC1P=d͕)z\Uqғ;MLz.BW 8t?}hWނϝޙP'O%G}Xt4L˫S=9yXD}g+] ǯ8QUa U0]m.Xgz9^?%V{5#v︷Xh/JrX830B ֍8AWͩE [ĹK DT? 8R   !"#$&'()*+,-./0123456789:;Oh+'0 `h    (0EMathematical Programming Relaxations for the Linear Ordering ProblemrLorenzoLorenzo8reMicrosoft PowerPointing@ 69@w@`{hGg  =  -- @ !--'@Arial-. 33-2 Mathematical Programming i)(  !)( ."System-@Arial-. 33=2 Ef$Relaxations for the Linear Ordering $    '  .-@Arial-. 332 Problema! (.-@Arial-. 32 mAdvisor: Prof. Moses Charikar   % ! .-@Arial-. 2 O(Lorenzo Orecchia    .-@Arial-. 2 'orecchia  .-@Arial-.  2 @(.-@Arial-. 2 O Fall 03   .-@Arial-. 2 OPcsJIWh %.-@Arial-. "2 hFinal Presentation    .-՜.+,0t