Smoothed analysis: introduction

• If we choose a large neighborhood, the smoothed complexity will be as low as the average case.

• A small neighborhood will approach the worst case.