Approximation and randomized algorithms

There are no prerequisites.

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

Arora, Sanjeev, and Boaz 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.

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

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.

Lectures, homeworks, and exercise groups.

Continuing (homework, practical work)
Final (written exam)
grading: 5 (fail), 6-10 (pass) (according to the Statute of UL)

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.