Vazirani, Vijay V.
Approximation algorithms / Vijay V. Vazirani. - Corr. 2nd print. - Berlin ; New York : Springer, c2003. - xix, 380 p. : ill. ; 25 cm.
Includes bibliographical references (p. [357]-372) and 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.
3540653678 (alk. paper) 9783540653677 (alk. paper)
2001042005
Computer algorithms.
Mathematical optimization.
QA76.9.A43 / V39 2003
511.8
Approximation algorithms / Vijay V. Vazirani. - Corr. 2nd print. - Berlin ; New York : Springer, c2003. - xix, 380 p. : ill. ; 25 cm.
Includes bibliographical references (p. [357]-372) and 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.
3540653678 (alk. paper) 9783540653677 (alk. paper)
2001042005
Computer algorithms.
Mathematical optimization.
QA76.9.A43 / V39 2003
511.8