Approximation algorithms / Vijay V. Vazirani.

Author
Vazirani, Vijay V. [Browse]
Format
Book
Language
English
Εdition
Corrected second printing.
Published/​Created
Berlin ; New York : Springer, c2003.
Description
xix, 380 p. : ill. ; 25 cm.

Details

Subject(s)
Bibliographic references
Includes bibliographical references (p. [357]-372) and index.
Contents
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.
ISBN
3540653678 (alk. paper)
OCLC
51739251
Statement on language in description
Princeton University Library aims to describe library materials in a manner that is respectful to the individuals and communities who create, use, and are represented in the collections we manage. Read more...
Other views
Staff view

Supplementary Information