线性规划与组合优化2015 发布站

主讲: 何斯迈 教授, simaihe@mail.shufe.edu.cn

Week 1-4:
Part 1: Basics of Linear Programming and Mixed Linear Integer Programming.
Part 2: Rounding and Primal-Dual type Algorithms.
Lecture Notes: UpdatedNote.pdf

Homework 1: HW1.pdf

Homework 2 (DUE APRIL 13th): HW2.pdf

Reference for Homework 2:
1. The Sample Average Approximation Method for Stochastic Discrete Optimization, Anton J. Kleywegt, Alexander Shapiro and Tito Homem-de-Mello. SIAM Journal on Optimization, 12(2), pp. 479-502, 2001. DOWNLOAD
2. Stability and Generalization, Olivier Bousquet and Andr′e Elisseeff. Journal of Machine Learning Research, 2, pp. 499-526, 2002. DOWNLOAD
3. A Dynamic Near-Optimal Algorithm for Online Linear Programming, Shipra Agrawal, Zizhuo Wang and Yinyu Ye. Operations Research 62(4), pp. 876-890, 2014. DOWNLOAD
4. Primal Beats Dual on Online Packing LPs in the Random-Order Model, Thomas Kesselheim, Klaus Radke, Andreas T¨onnis and Berthold V¨ocking. STOC’14, pp. 303-321, 2014. DOWNLOAD

Week 5: SDP Relaxation for Max Cut Problem
Lecture Notes: MaxCut.pdf
References:
Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming, Michel X. Goemans and David P. Williamson, Journal of the Association for Computing Machinery, 42(6), pp. 1115-1145, 1995. DOWNLOAD
A .699-approximation algorithm for Max-Bisection, Yinyu Ye, Mathematical Programming Series A, 90, pp. 101-111, 2001. DOWNLOAD

Week 7: Online Linear Programming
Lecture Notes: OnlineLP.pdf

Week 8: Dual Fitting and Primal-Dual Schema
Week 9: Facility Location Problems
Lecture Notes: PrimalDual.pdf

Week 10: SDP and Matrix Decomposition (by Prof. Bo Jiang)
Lecture Notes (by Prof. Shuzhong Zhang): Lecture7.pdf

Week 11: Submodular Functions and Their Applications
Lecture Notes: SODA-plenary-talk.pdf Lecture_Series.pdf B23-10.pdf

最后更新: 2015.05.09