APPROXIMATION ALGORITHMS

VAZIRANI VIJAY V.

ISBN 10: 8181283856 ISBN 13: 9788181283856

Publisher: SPRINGER (SIE), 2013

Synopsis

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 time algorithms, therefore becomes a compelling subject of scientific inquiry in computer science and mathematics. This book presents the theory of ap­ proximation algorithms as it stands today. It is reasonable to expect the picture to change with time. This book is divided into three parts. In Part I we cover combinato­ rial algorithms for a number of important problems, using a wide variety of algorithm design techniques. The latter may give Part I a non-cohesive appearance. However, this is to be expected - nature is very rich, and we cannot expect a few tricks

Edition details

• Publisher: SPRINGER (SIE)
• Publication date: 2013
• ISBN 10: 8181283856
• ISBN 13: 9788181283856
• Binding: Unknown Binding
• Language: English
• Number of pages: 660