SubjectsSubjects(version: 845)
Course, academic year 2018/2019
   Login via CAS
Approximation and Online Algorithms - NDMI018
Title in English: Aproximační a online algoritmy
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2018 to 2018
Semester: summer
E-Credits: 6
Hours per week, examination: summer s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: not taught
Language: Czech, English
Teaching methods: full-time
Additional information:
Guarantor: prof. RNDr. Jiří Sgall, DrSc.
Class: Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Discrete Mathematics
Annotation -
Last update: (11.05.2015)
For many optimization problems it is impossible to find an optimal solution fast. In such case, it is important to study approximation algorithms that work faster, but the solution they find is not necessarily an optimal one. Sometimes, we also have to react to partial input without knowledge of the complete input, by building a solution step by step. Such algorithms are called on-line. The subject of the course is the study of these two classes of algorithms. We assume knowledge on the level of the Bc. course NDMI084 Introduction to approximation and randomized algorithms.
Aim of the course -
Last update: (11.05.2015)

Teach the students selected techniques of design and analysis of approximation and online algorithms.

Course completion requirements -
Last update: prof. RNDr. Jiří Sgall, DrSc. (04.03.2018)

To pass the tutorials it is required to get at least a half of total points for homeworks assigned during the semester conditioned on regular attendance. If the student does not attend the tutorials regularly, two thirds of total points will be required. Due to the requirements, additional attempts to pass the tutorial are not allowed.

The exam is oral. The requirements correspond to the syllabus as covered by the lectures. Passing the turorials is required before taking the exam.

Literature -
Last update: (11.05.2015)
  • D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, Cambridge university press, 2011.
  • V. V. Vazirani: Approximation Algorithms, Springer, 2001.
  • A. Borodin, R. El-Yaniv: Online computation and competitive analysis. Cambridge university press, 1998.
  • A. Fiat, G. Woeginger: Online Algorithms - The State of the Art, LNCS 1442, Springer, 1998.

Syllabus -
Last update: (11.05.2015)

Techniques covered:

  • Basic definitions, approximation and competitive ratio
  • Polynomial-time approximation schemes, their relation to strong NP-hardness
  • Advanced use of linear programming in approximation algorithms: rounding, primal-dual algorithms
  • Use of semidefinite programming in approximation algorithms
  • Use of potential functions for online algorithms
  • Methods for proving the hardness of approximation: L-reductions, APX-completeness, PCP theorem

Problems and algorithms covered:

  • Various models of scheduling and bin packing, greedy algorithms, further approximation and online algorithms
  • Combinatorial problems: Steiner trees, maximal cut, coloring
  • Online algorithms for paging (caching) and k-server problem
  • Online algorithms for navigation in an unknown environment

Charles University | Information system of Charles University |