Table of contents for Approximation algorithms / Vijay V. Vazirani.
Bibliographic record and links to related information available from the Library of Congress catalog
Information from electronic data provided by the publisher. May be incomplete or contain other coding.
Introduction.- I. Combinatorial Algorithms: Set cover. Steiner tree and TSP. Multiway cuts and k-cuts. k-center. Feedback vertex set. Shortest superstring. Knapsack. Bin packing. Minimum makespan scheduling. Euclidean TSP.- II. LP-Based Algorithms: Introduction to LP-duality. Rounding applied to set cover. LP-duality based analysis for set cover. 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.- III. Other Topics: Counting problems. Shortest vector. Hardness of approximation. Open problems.
Library of Congress subject headings for this publication: