Approximation Algorithms - Vazirani Vijay-V

. .

Résumé :
The field of approximation algorithms, perhaps the most active area of algorithmic research today, combines a rich and deep mathematical theory with the promise of profound practical impact. Most computational problems arising across a very broad spectrum of application areas, such as VLSI design, design and operation of networks, web-related problems, scheduling, manufacturing, game theory, biology, and number theory, are NP-hard, hence making their exact solution prohibitively time-consuming. This challenge has motivated the growth of an impressive literature, providing approximation algorithms for this very diverse collection of problems. A slew of spectacular results in the last decade has revolutionized the field. The challenge met by this book is to capture the beauty and excitement of work in this thriving field and to convey in a lucid manner the underlying theory and methodology. Many of the research results presented have been simplified, and new insights provided Perhaps the most important aspect of the book is that it shows simple ways of talking about complex, powerful algorithmic ideas by giving intuitive proofs, by writing algorithms in plain English, and by providing numerous critical examples and illustrations. This book will be of interest to the scientific community at large and, in particular, to students and researchers in Computer Science, Operations Research, and Discrete Mathematics. It can be used both as a text in a graduate course on approximation algorithms and as a supplementary text in basic undergraduate and graduate courses on algorithms.

Biographie:
Vijay Vazirani got his Bachelors degree in Computer Science from MIT in 1979, and his Ph.D. from U.C. Berkeley in 1983. His research career, which spans over twenty years, has been centred around the design of algorithms, together with work on complexity theory, cryptography, coding theory, and game theory. During the first ten years, he made seminal contributions to the classical maximum matching problem which has historically played a central role in the development of the theory of algorithms. Over the last ten years he has had much influence on the emerging theory of approximation algorithms through work on several of its fundamental problems. Besides his academic duties as Professor of Computer Science at Georgia Tech, he serves on the Board of Directors of Primitive Root, Inc., an Internet security company, of which he is also a co-founder.

Sommaire:
["COMBINATORIAL ALGORITHMS","Set cover","Steiner tree and TSP","Multiway cut and k-cut","K-center","Feedback vertex set","Shortest superstring","Knapsack","Bin packing","Minimum makespan scheduling","Euclidean TSP","LP-BASED ALGORITHMS","Introduction to LP-duality","Set cover via dual fitting","Rounding applied to set cover","Set cover via the primal-dual shema","Maximum satisfiability","Scheduling on unrealated parallel machines","Multicut and integer multicommodity flow in trees","Multiway cut","Multicut in general graphs","Sparset cut","Steiner forest","Steiner network","Facility location","K-median","Semidefinite programming","OTHER TOPICS","Shortest vector","Counting problems","Hardness of approximation","Open problems."]