The Design of Approximation Algorithms

约 257 个字 预计阅读时间 1 分钟

作者 David P. Williamson 和 David B. Shmoys

谁懂组会开幕 LP 然后想等 LP 以后的结论结果到组会结束还在 LP 的救赎感

Table of Contents

Section 1

• 1. An Introduction to Approximation Algorithms
• 2. Greedy Algorithms and Local Search
• 3. Rounding data and dynamic programming
• 4. Deterministic rounding of Linear Programs
• 5. Random sampling and randomized rounding of Linear Programs
• 6. Randomized rounding of semidefinite programs
• 7. The primal-dual method
• 8. Cuts and metrics

25-26 秋冬学期组合优化讨论班安排

Part 1: 线性规划基础

单纯形算法 对偶基础回顾、对偶单纯形法 原始-对偶方法及其应用(PAPADIMITRIOU Chapter 5-7) 最大流算法(PAPADIMITRIOU Chapter 9) 贪心算法、拟阵(PAPADIMITRIOU Chapter 12)

Part 2：线性整数规划

Models：Packing, Covering, Partitioning(Integer Programming Chapter 2.4) (简单介绍上述三种模型) 割平面法(PAPADIMITRIOU Chapter 14) 分枝定界法(PAPADIMITRIOU Chapter 18) 整数规划基于LP松弛的近似和原始对偶近似

Part 3 经典问题讲解

Algorithms for matching and weighted matching Approximation algorithms for packing, covering and partitioning problems(PAPADIMITRIOU Chapter 17) 斯坦纳树、旅行商问题 Local Search(PAPADIMITRIOU Chapter 19)