Announcement
- This is an open seminar to students who are interested in approximation algorithm designs, especially those who come from Department of Computer Science, Shanghai Jiao Tong University.
- We are also learners in this direction, so welcome to point out any mistakes/misunderstandings in our lectures and notes.
General Information
- Level: Undergraduate (Junior & Senior), Graduate
- Time & Place:
- 2:00pm – 4:00pm, Wednesday, Telecom BULD 3-308 (电信群楼3-308)
- Presenters:
- Name: Xiaofeng Gao (高晓沨)
- Email: gao-xf(at)cs.sjtu.edu.cn
- Office: Telecom Building 3-543
- Phone: 021-34207407
- Name: Chihao Zhang (张驰豪)
- Email: chihao.zhang(at)gmail.com
- Office: Telecom Building 3-325
- Phone: 021-34205060
Lectures and Notes
Lecture 1: Introduction to Approximation Algorithm (9/20/2012)
- Lecture Notes
- Introduction to Approximation: Slide01-IntroductionToAA.pdf
- Reference
- Introduction to Approximation: Slide01-IntroductionToAA.pdf
Lecture 2: Linear Programming and Primal-Dual Schema (10/09/2012)
- Lecture Notes
- LP and Primal-Dual : Slide02-LP&PrimalDual.pdf
- Handout Version: Slide02-LP&PrimalDual-Handout.pdf
Lecture 3: Approximations for MAX-SAT Problem (10/23/2012)
- Lecture Notes
- LP and Primal-Dual : Slide03-MAXSAT.pdf
- Handout Version: Slide03-MAXSAT-Handout.pdf
Lecture 4: Greedy Strategy (I) (11/06/2012)
- Lecture Notes
- Greedy Strategy (I): Slide04-GreedyStrategy1.pdf
- Pseudocode Standard: http://users.csc.calpoly.edu/~jdalbey/SWE/pdl_std.html
http://www.coderookie.com/2006/tutorial/the-pseudocode-programming-process/
Lecture 5-6: Steiner Tree Problems (11/20/2012 & 12/04/2012)
- Lecture Notes
- Steiner Tree Problems: Slide0506-SteinerTree.pdf
- Handout Version: Slide0506-SteinerTree-Handout.pdf
Lecture 7: Semi-Definite Programming (3/27/2013)
- Lecture Notes
- Steiner Tree Problems: Slide0506-SteinerTree.pdf
- Handout Version: Slide0506-SteinerTree-Handout.pdf
References
- Approximation Algorithms
- Rajeev Motwani, Lecture Notes on Approximation Algorithms (Volumn I), 1991.
- Hochbaum (Editor), Approximation Algorithms for NP-Hard Problems, 1997.
- Ausiello, Crescenizi, Gambosi, etc., Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, 1999.
- Vijay V. Vazirani, Approximation Algorithms, 2001.
- D.P. Williamson and D.B. Shmoys, The Design of Approximation Algorithms, 2011.
- D.Z Du, K-I. Ko, and X.D. Hu, Design and Analysis of Approximation Algorithms, 2012.
- Algorithm Designs
- S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Algorithms, 2007.
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, 2009.
- Jon Kleinberg, Algorithm Design, 2012.
- Other Related Materials
- M.R. Garey and D.S. Johnson: Computers and Intractability: A guide to the Theory of NP-Completeness, 1979.
- C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, 1998.
