Approximation algorithms

Author(s)

Bibliographic Information

Approximation algorithms

Vijay V. Vazirani

Springer, c2001

Other Title

Appromixation algorithms

Available at  / 26 libraries

Search this Book/Journal

Note

Includes bibliographical references (p. [355]-370) and indexes

Misprint in title page title (TT).

Description and Table of Contents

Description

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.

Table of Contents

1 Introduction.- I. Combinatorial Algorithms.- 2 Set Cover.- 3 Steiner Tree and TSP.- 4 Multiway Cut and k-Cut.- 5 k-Center.- 6 Feedback Vertex Set.- 7 Shortest Superstring.- 8 Knapsack.- 9 Bin Packing.- 10 Minimum Makespan Scheduling.- 11 Euclidean TSP.- II. LP-Based Algorithms.- 12 Introduction to LP-Duality.- 13 Set Cover via Dual Fitting.- 14 Rounding Applied to Set Cover.- 15 Set Cover via the Primal-Dual Schema.- 16 Maximum Satisfiability.- 17 Scheduling on Unrelated Parallel Machines.- 18 Multicut and Integer Multicommodity Flow in Trees.- 19 Multiway Cut.- 20 Multicut in General Graphs.- 21 Sparsest Cut.- 22 Steiner Forest.- 23 Steiner Network.- 24 Facility Location.- 25 k-Median.- 26 Semidefinite Programming.- III. Other Topics.- 27 Shortest Vector.- 28 Counting Problems.- 29 Hardness of Approximation.- 30 Open Problems.- A An Overview of Complexity Theory for the Algorithm Designer.- A.3.1 Approximation factor preserving reductions.- A.4 Randomized complexity classes.- A.5 Self-reducibility.- A.6 Notes.- B Basic Facts from Probability Theory.- B.1 Expectation and moments.- B.2 Deviations from the mean.- B.3 Basic distributions.- B.4 Notes.- References.- Problem Index.

by "Nielsen BookData"

Details

Page Top