Approximation algorithms

Covering the basic techniques used in the latest research work, the author consolidates progress made so far, including some very recent and promising results, and conveys the beauty and excitement of work in the field. He gives clear, lucid explanations of key results and ideas, with intuitive proofs, and provides critical examples and numerous illustrations to help elucidate the algorithms. Many of the results presented have been simplified and new insights provided. Of interest to theoretical computer scientists, operations researchers, and discrete mathematicians. 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.--jacket. 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 Schema -- Maximum Satisfiability -- Scheduling On Unrelated Parallel Machines -- Multicut And Integer Multicommodity Flow In Trees -- Multiway Cut -- Multicut In General Graphs -- Sparsest Cut -- Steiner Forest -- Steiner Network -- Facility Location -- K-median -- Semidefinite Programming -- Other Topics -- Shortest Vector -- Counting Problems -- Hardness Of Approximation -- Open Problems -- An Overview Of Complexity Theory For The Algorithm Designer -- Basic Facts From Probability Theory. Vijay V. Vazirani. Includes Bibliographical References (p. [355]-370) And Index. 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 to help solve the diverse collection of NP-hard problems. Indeed, in this part, we have purposely refrained from tightly cat­ egorizing algorithmic techniques so as not to trivialize matters. Instead, we have attempted to capture, as accurately as possible, the individual character of each problem, and point out connections between problems and algorithms for solving them. "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."--BOOK JACKET Approximation algorithms are currently a central and fast-developing area of research in theoretical computer science. This monograph covers the basic techniques used in the latest research work, techniques that everyone in the field should know, and shows that they form the beginnings of a promising theory. The author consolidates progress made so far, including some very recent results, and makes a strong effort to convey the beauty and excitement of work in the field.