Introduction Combinatorial Approach Linear thinking Provable approximation: LP Semi-definite programming (SDPs) Duality Introduction of the Course Chapter 1 Approximation Algorithms Advanced Algorithms U CAS 20, Feb, 2017 Introduction Combinatorial Approach Linear thinking Provable approximation: LP Semi-definite programming (SDPs) Duality Advanced Algorithms 1. Definition of algorithms? How many definitions you can give? 2. What are the roles of algorithms? • The engines of computer 3. What is advanced? approximately after 1990 • Randomized • Approximation • Local algorithms • Dynamical algorithms 4. New direction? Introduction Combinatorial Approach Linear thinking Provable approximation: LP Semi-definite programming (SDPs) Duality The goal of the course 1. Better understanding of the art 2. The key of algorithms? • New ideas • New applications • New understanding of the concept of computation Computation vs Game, Learning, Evolution etc 3. Examination The
