07980cam a2200361 a 4500001001000000003000600010005001700016008004100033010001500074020002900089020002600118035002100144040004900165042000800214050002100222082001900243100002500262245008400287260005100371300003300422504005300455505090600508505100001414505102102414505099203435505098804427505078905415520124606204650002607450650003107476700002707507856008407534671709856OCoLC20150408114107.0110114s2011    nyua     b    001 0 eng    a2011001945  a9780521195270 (hardback)  a0521195276 (hardback)  a(OCoLC)671709856  aDLCcDLCdYDXdBTCTAdYDXCPdCDXdGIKBMdINU  apcc00aQA221b.W55 201100a518.5222bWDD1 aWilliamson, David P.14aThe design of approximation algorithms /cDavid P. Williamson, David B. Shmoys.  aNew York :bCambridge University Press,c2011.  axi, 504 p. :bill. ;c26 cm.  aIncludes bibliographical references and indexes.00gMachine 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.00g3.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.00g5.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.00g7.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.00g10.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.00g14.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.  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"-- 0aApproximation theory. 0aMathematical optimization.1 aShmoys, David Bernard.423Cover imageuhttp://assets.cambridge.org/97805211/95270/cover/9780521195270.jpg