6/ 19 1. Erweiterung  m > 2 1. Strategie : Doubling auf m > 2 (d.h. Suchtiefenverdopplung nach jeder Runde) worst case: in der Runde mit der Suchtiefe 2^j wird der Zielpunkt auf  der  Halbgerade  m_j  um  ein  ƒÃ  verfehlt,  darauf  hin beginnt eine neue Runde mit der Suchtiefe 2^j+1. Suchtiefe  : 2^j j f   = Weglänge bis zur Runde 2^j  : 0 2 2 j i i m = å Weglänge der neuen Runde  : ( ) 1 2 1 2^j m + - Weglänge von s zu t (K_OPT)  :   2^j    e + Kompetitivitätsbeweis : ( ) ( ) ( ) 1 0 1 0 1 1 2 2 2 1 2 2 2 2 2 2 1 2 2                     2 2 2 2 2 1 2                     1 2                     8 3 j i j j S i j OPT j i j j i j j j j j m m K C K m m m m m e e e e e + = + = + + + - + + ® = = + + - + = + + + + - £ + = - å å Der Kompetitivitätsfaktor ist also    8 3 m £ -