Skip to main content

Approximation and randomized algorithms

2026/2027
Programme:
Computer Science and Mathematics, Second Cycle
Year:
1 ali 2 year
Semester:
first
Kind:
optional
ECTS:
6
Language:
slovenian
Course director:

Uroš Čibej

Hours per week – 1. semester:
Lectures
3
Seminar
0
Tutorial
2
Lab
0
Content (Syllabus outline)

Course Structure

Advanced Topics in Computational Complexity

Approximation Algorithms

Randomized Algorithms

Other Techniques for Tackling Complexity

________________________________________

Advanced Topics in Computational Complexity

This part of the course will delve into the hierarchy of computational complexity. We will cover:

Various computational models

Important classes such as P, NP, PH, PSPACE, ECP, and NEXP

The role and examples of reductions between these classes

The concept of relativization (oracles)

Ladner's theorem and examples of problems like graph isomorphism (GI) and factorization

Modeling problems with Boolean satisfiability (SAT), integer linear programming (ILP), and semidefinite programming (SDP)

________________________________________

Approximation Algorithms

This section will focus on algorithms that guarantee solutions with a certain deviation from the optimal one. The topics include:

Definitions of approximation algorithms and the APX class

Design methods such as:

Greedy algorithms

Linear programming

Semidefinite programming

Polynomial-time approximation schemes (PTAS)

Algorithms with a constant approximation ratio

L-reductions within the APX class

________________________________________

Randomized Algorithms

We will explore how randomness can help in solving difficult problems. This includes:

The use of randomness for problems in the P class, for example, with the Rabin-Miller and Karger algorithms, and checking for polynomial identity

The use of randomness for approximation

The color coding method

The concept of derandomization, which converts randomized algorithms into deterministic ones

________________________________________

Other Techniques for Tackling Complexity

Finally, we will get acquainted with other approaches, such as:

Fixed-parameter tractable algorithms (FPT) and kernelization

Quantum algorithms

Circuit complexity

Exact exponential algorithms

Readings

Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009

D.P. Williamson, D.B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.

V. V. Vazirani, Approximation Algorithms, Springer, 2004.

D. Hochbaum, Approximation Algorithms for NP-hard Problems, Course Technology, 1996.

R. Motwani, P.Raghavan, Randomized Algorithms, Cambridge University Press, 1995.

M. Mitzenmacher, E. Upfal, Probability and Computing: Randomized algorithms and Probabilistic Analysis, Cambridge University Press, 2005.

Objectives and competences

Students will learn, both theoretically  and through practical examples,  how to use approximation and randomization techniques  to solve practical yet intractable computational problems.

Intended learning outcomes

After completing the course, the student will be able to:

Understand the reasons for using approximation and randomized approaches to solve complex problems, such as NP-hard problems.

Develop a deep understanding of the hierarchy of computational complexity classes (P, NP, PH, PSPACE, etc.), the relationships between them, and the role of different types of reductions.

Grasp the theoretical foundations of approximation algorithms, including definitions, design methods (greedy algorithms, linear and semidefinite programming), and ways to evaluate the quality of solutions (APX class, PTAS, L-reductions).

Understand the role of randomness in algorithm development and differentiate between various types of randomized algorithms and the complexity classes that describe them.

Learn about other modern techniques for tackling computational complexity, such as fixed-parameter tractable algorithms, quantum algorithms, circuit complexity, and exact exponential algorithms.

Become proficient in using various methods for the design and analysis of both approximation and randomized algorithms.

Be capable of independently searching for and understanding new research results in the field of approximation and randomized solutions to computational problems.

Learning and teaching methods

Lectures, homeworks, and exercise groups.

Assessment

Type (examination, coursework, project):

Continuing (homework, practical work)
Final (written exam)
5 - 10, a student passes the exam if he is graded from 6 to 10

Lecturer's references
  1. ČIBEJ, Uroš, LI, Aaron, MIKLÓS, István, NASIR, Sohaib, SRIKANTH, Varun. Constructing bounded degree graphs with prescribed degree and neighbor degree sequences. Discrete Applied Mathematics, 2023.
  2.   ČIBEJ, Uroš, SLIVNIK, Boštjan, ROBIČ, Borut. The complexity of static data replication in data grids. Parallel Computing, 2007.
  3.   ČIBEJ, Uroš, ROBIČ, Borut, MIHELIČ, Jurij. Empirical estimation of the halting probabilities. Computability in Europe, 2014.
  4.   ČIBEJ, Uroš, MIHELIČ, Jurij. Improvements to Ullmann’s algorithm for the subgraph isomorphism problem. International Journal of Pattern Recognition and Artificial Intelligence.
  5.   ČIBEJ, Uroš, MIHELIČ, Jurij. A polynomial-time algorithm for recognizing subgraph-symmetry-compressible graphs. MATCOS, 2019.
  6.   ČIBEJ, Uroš, FÜRST, Luka, MIHELIČ, Jurij. A symmetry-breaking node equivalence for pruning the search space in backtracking algorithms. Symmetry, 2019.