000			02051cam a22002414a 4500
020			_a3540653678 (alk. paper)
020			_a9783540653677
020			_a3642084699
020			_a9783642084690
082	0	0	_a005.1 _bVAZ
100	1		_aVazirani, Vijay V.
245	1	0	_aApproximation algorithms
260			_aBerlin ; _aNew York : _bSpringer, _cc2001.
300			_axix, 378 p. : _billustrations ;
500			_aIncluded Problem, Subject Index.
505			_aCombinatorial 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.
520			_a"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,
650		0	_aComputer algorithms.
650		0	_aMathematical optimization.
856	4	2	_uhttp://www.loc.gov/catdir/enhancements/fy0816/2001042005-d.html
856	4	1	_uhttp://www.loc.gov/catdir/enhancements/fy0816/2001042005-t.html
942			_cREF
999			_c11189 _d11189