Normal view MARC view ISBD view

Approximation algorithms

By: Vazirani, Vijay VMaterial type: Text

TextPublication details: Berlin ; New York : Springer, c2001Description: xix, 378 p. : illustrationsISBN: 3540653678 (alk. paper); 9783540653677 ; 3642084699 ; 9783642084690Subject(s): Computer algorithms | Mathematical optimizationDDC classification: 005.1 Online resources: Click here to access online | Click here to access online

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.

Summary: "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,

Tags from this library: No tags from this library for this title. Log in to add tags.

Average rating: 0.0 (0 votes)

Holdings ( 1 )
Title notes ( 3 )
Comments ( 0 )

Holdings
Item type	Current library	Collection	Call number	Status	Date due	Barcode	Item holds
Reference Books	Main Library Reference	Reference	005.1 VAZ (Browse shelf(Opens below))	Available		009878

Total holds: 0

Browsing Main Library shelves, Shelving location: Reference, Collection: Reference Close shelf browser (Hides shelf browser)

Previous								Next
Previous	005.1 SOM Software engineering /	005.1 SOM Software engineering /	005.1 STE Applied software project management /	005.1 VAZ Approximation algorithms	005.1 WES Instant notes in Bioinformatics	005.1 WIL Parallel programming : techniques and applications using networked workstations and parallel computers	005.1 WIL Practical Parallel Programming	Next

Included Problem, Subject Index.

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.

"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,

There are no comments on this title.

to post a comment.