000			08063cam a2200385 a 4500
001			671709856
003			OCoLC
005			20150408114107.0
008			110114s2011 nyua b 001 0 eng
010			_a2011001945
020			_a9780521195270 (hardback)
020			_a0521195276 (hardback)
035			_a(OCoLC)671709856
040			_aDLC _cDLC _dYDX _dBTCTA _dYDXCP _dCDX _dGIKBM _dINU
042			_apcc
050	0	0	_aQA221 _b.W55 2011
082	0	0	_a518.5 _222 _bWDD
100	1		_aWilliamson, David P. _919125
245	1	4	_aThe design of approximation algorithms / _cDavid P. Williamson, David B. Shmoys.
260			_aNew York : _bCambridge University Press, _c2011.
300			_axi, 504 p. : _bill. ; _c26 cm.
504			_aIncludes bibliographical references and indexes.
505	0	0	_gMachine generated contents note: _gI. _tAn Introduction to the Techniques -- _g1. _tAn Introduction to Approximation Algorithms -- _g1.1. _tThe Whats and Whys of Approximation Algorithms -- _g1.2. _tAn Introduction to the Techniques and to Linear Programming: The Set Cover Problem -- _g1.3. _tA Deterministic Rounding Algorithm -- _g1.4. _tRounding a Dual Solution -- _g1.5. _tConstructing a Dual Solution: The Primal-Dual Method -- _g1.6. _tA Greedy Algorithm -- _g1.7. _tA Randomized Rounding Algorithm -- _tExercises -- _tChapter Notes -- _g2. _tGreedy Algorithms and Local Search -- _g2.1. _tScheduling Jobs with Deadlines on a Single Machine -- _g2.2. _tThe k-Center Problem -- _g2.3. _tScheduling Jobs on Identical Parallel Machines -- _g2.4. _tThe Traveling Salesman Problem -- _g2.5. _tMaximizing Float in Bank Accounts -- _g2.6. _tFinding Minimum-Degree Spanning Trees -- _g2.7. _tEdge Coloring -- _tExercises -- _tChapter Notes.
505	0	0	_g3. _tRounding Data and Dynamic Programming -- _g3.1. _tThe Knapsack Problem -- _g3.2. _tScheduling Jobs on Identical Parallel Machines -- _g3.3. _tThe Bin-Packing Problem -- _tExercises -- _tChapter Notes -- _g4. _tDeterministic Rounding of Linear Programs -- _g4.1. _tMinimizing the Sum of Completion Times on a Single Machine -- _g4.2. _tMinimizing the Weighted Sum of Completion Times on a Single Machine -- _g4.3. _tSolving Large Linear Programs in Polynomial Time via the Ellipsoid Method -- _g4.4. _tThe Prize-Collecting Steiner Tree Problem -- _g4.5. _tThe Uncapacitated Facility Location Problem -- _g4.6. _tThe Bin-Packing Problem -- _tExercises -- _tChapter Notes -- _g5. _tRandom Sampling and Randomized Rounding of Linear Programs -- _g5.1. _tSimple Algorithms for MAX SAT and MAX CUT -- _g5.2. _tDerandomization -- _g5.3. _tFlipping Biased Coins -- _g5.4. _tRandomized Rounding -- _g5.5. _tChoosing the Better of Two Solutions -- _g5.6. _tNonlinear Randomized Rounding -- _g5.7. _tThe Prize-Collecting Steiner Tree Problem.
505	0	0	_g5.8. _tThe Uncapacitated Facility Location Problem -- _g5.9. _tScheduling a Single Machine with Release Dates -- _g5.10. _tChernoff Bounds -- _g5.11. _tInteger Multicommodity Flows -- _g5.12. _tRandom Sampling and Coloring Dense 3-Colorable Graphs -- _tExercises -- _tChapter Notes -- _g6. _tRandomized Rounding of Semidefinite Programs -- _g6.1. _tA Brief Introduction to Semidefinite Programming -- _g6.2. _tFinding Large Cuts -- _g6.3. _tApproximating Quadratic Programs -- _g6.4. _tFinding a Correlation Clustering -- _g6.5. _tColoring 3-Colorable Graphs -- _tExercises -- _tChapter Notes -- _g7. _tThe Primal-Dual Method -- _g7.1. _tThe Set Cover Problem: A Review -- _g7.2. _tChoosing Variables to Increase: The Feedback Vertex Set Problem in Undirected Graphs -- _g7.3. _tCleaning Up the Primal Solution: The Shortest s-t Path Problem -- _g7.4. _tIncreasing Multiple Variables at Once: The Generalized Steiner Tree Problem -- _g7.5. _tStrengthening Inequalities: The Minimum Knapsack Problem -- _g7.6. _tThe Uncapacitated Facility Location Problem.
505	0	0	_g7.7. _tLagrangean Relaxation and the k-Median Problem -- _tExercises -- _tChapter Notes -- _g8. _tCuts and Metrics -- _g8.1. _tThe Multiway Cut Problem and a Minimum-Cut -- Based Algorithm -- _g8.2. _tThe Multiway Cut Problem and an LP Rounding Algorithm -- _g8.3. _tThe Multicut Problem -- _g8.4. _tBalanced Cuts -- _g8.5. _tProbabilistic Approximation of Metrics by Tree Metrics -- _g8.6. _tAn Application of Tree Metrics: Buy-at-Bulk Network Design -- _g8.7. _tSpreading Metrics, Tree Metrics, and Linear Arrangement -- _tExercises -- _tChapter Notes -- _gII. _tFurther Uses of the Techniques -- _g9. _tFurther Uses of Greedy and Local Search Algorithms -- _g9.1. _tA Local Search Algorithm for the Uncapacitated Facility Location Problem -- _g9.2. _tA Local Search Algorithm for the k-Median Problem -- _g9.3. _tMinimum-Degree Spanning Trees -- _g9.4. _tA Greedy Algorithm for the Uncapacitated Facility Location Problem -- _tExercises -- _tChapter Notes -- _g10. _tFurther Uses of Rounding Data and Dynamic Programming.
505	0	0	_g10.1. _tThe Euclidean Traveling Salesman Problem -- _g10.2. _tThe Maximum Independent Set Problem in Planar Graphs -- _tExercises -- _tChapter Notes -- _g11. _tFurther Uses of Deterministic Rounding of Linear Programs -- _g11.1. _tThe Generalized Assignment Problem -- _g11.2. _tMinimum-Cost Bounded-Degree Spanning Trees -- _g11.3. _tSurvivable Network Design and Iterated Rounding -- _tExercises -- _tChapter Notes -- _g12. _tFurther Uses of Random Sampling and Randomized Rounding of Linear Programs -- _g12.1. _tThe Uncapacitated Facility Location Problem -- _g12.2. _tThe Single-Source Rent-or-Buy Problem -- _g12.3. _tThe Steiner Tree Problem -- _g12.4. _tEverything at Once: Finding a Large Cut in a Dense Graph -- _tExercises -- _tChapter Notes -- _g13. _tFurther Uses of Randomized Rounding of Semidefinite Programs -- _g13.1. _tApproximating Quadratic Programs -- _g13.2. _tColoring 3-Colorable Graphs -- _g13.3. _tUnique Games -- _tExercises -- _tChapter Notes -- _g14. _tFurther Uses of the Primal-Dual Method.
505	0	0	_g14.1. _tThe Prize-Collecting Steiner Tree Problem -- _g14.2. _tThe Feedback Vertex Set Problem in Undirected Graphs -- _tExercises -- _tChapter Notes -- _g15. _tFurther Uses of Cuts and Metrics -- _g15.1. _tLow-Distortion Embeddings and the Sparsest Cut Problem -- _g15.2. _tOblivious Routing and Cut-Tree Packings -- _g15.3. _tCut-Tree Packings and the Minimum Bisection Problem -- _g15.4. _tThe Uniform Sparsest Cut Problem -- _tExercises -- _tChapter Notes -- _g16. _tTechniques in Proving the Hardness of Approximation -- _g16.1. _tReductions from NP-Complete Problems -- _g16.2. _tReductions that Preserve Approximation -- _g16.3. _tReductions from Probabilistically Checkable Proofs -- _g16.4. _tReductions from Label Cover -- _g16.5. _tReductions from Unique Games -- _tChapter Notes -- _g17. _tOpen Problems.
520			_a"Discrete optimization problems are everywhere, from traditional operations research planning problems, such as scheduling, facility location, and network design; to computer science problems in databases; to advertising issues in viral marketing. Yet most such problems are NP-hard. Thus unless P = NP, there are no efficient algorithms to find optimal solutions to such problems. This book shows how to design approximation algorithms: efficient algorithms that find provably near-optimal solutions. The book is organized around central algorithmic techniques for designing approximation algorithms, including greedy and local search algorithms, dynamic programming, linear and semidefinite programming, and randomization. Each chapter in the first part of the book is devoted to a single algorithmic technique, which is then applied to several different problems. The second part revisits the techniques but offers more sophisticated treatments of them. The book also covers methods for proving that optimization problems are hard to approximate. Designed as a textbook for graduate-level algorithms courses, the book will also serve as a reference for researchers interested in the heuristic solution of discrete optimization problems"--
650		0	_aApproximation theory. _919126
650		0	_aMathematical optimization. _912151
700	1		_aShmoys, David Bernard. _919127
856	4	2	_3Cover image _uhttp://assets.cambridge.org/97805211/95270/cover/9780521195270.jpg
942			_2ddc _cDVD
999			_c26676 _d261176