Approximation Algorithms - Paperbackby Vijay V. Vazirani (Author) Although this may seem a paradox, all exact science is dominated by the idea of approximation. Bertrand Russell (1872 1970) Most natural optimization problems, including those arising in important application areas, are NP hard. Therefore, under the widely believed con jecture that P = = NP, their exact solution is prohibitively time consuming. Charting the landscape of approximability of these problems, via polynomial