Approximation and randomized algorithms

There are no prerequisites.

The course will offer the following themes:
Introduction
Computational complexity of decision and optimization problems
NP-complete and NP-hard problems
Heuristic algorithms, quality of suboptimal solutions, (non)existence of a guarantee of quality
Approximate solving of NP-hard problems
Approximation algorithms
Quality of approximate solutions
The class APX
Gap technique
Approximation schemes
The classes PTAS and FPTAS
Limits of approximate solving
The design of approximation algorithms
Greedy method
Focusing on subproblems
Iterative partitioning
Dynamic programming
Randomized solving of NP-hard problems
Las Vegas and Monte Carlo algorithms
The classes RP, co-RP, ZPP, PP, BPP
The design of randomized algorithm
Random sampling
Establishing abundance of witnesses
Random reordering
Hashing
Load balancing

B. Robič, Aproksimacijski algoritmi, Založba FE in FRI, 2.izd., 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.

Knowledge and understanding:
After completing the course the student will:

-- understand the reasons for approximative or randomized approach to solving of (mainly NP-hard) computational problems,
-- understand the differences (and connections) between decision and optimization problems,
-- understand the practical reasons for approx. or rand. computing of suboptimal solutions,
-- understand the basic notions about approx. and rand. algorithms,
-- understand different approaches to estimation of the quality of suboptimal solutions, and their limitations,
-- undertand the complexity classes of decision and optimizations problems according to their amenability to approx. or rand. solving, and the relations between the classes,
-- know approx. or rand. algorithms for selected importand NP-hard problems,
-- be able to use different methods of the design and analysis of approx. and rand. algorithms,
-- be able to follow and understand the new research results in the area of approximation and randomized algorithms

Lectures, homeworks, and exercise groups.

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

B.Robič, The Foundations of Computability Theory, Spinger, 2015. (ISBN 978-3662448076)
M.Bezenšek, B.Robič, A survey of parallel and distributed algorithms for the Steiner tree problem. Int. J. Par. Program., 42:287-319, 2013.
J.Mihelič, A.Mahjoub, C.Rapine, B.Robič, Two-stage flexible-choice problems under uncertainty. Eur. J. Oper. Res. 201(2):399-403, 2010.
J.Mihelič, B.Robič, Flexible-attribute problems. Comput. Optim. Appl. 47(3):553-566, 2010.
R.Trobec, M.Šterk, B.Robič, Computational complexity and parallelization of the meshless local Petrov-Galerkin methods. Comput. Struct. 87(1):81-90,2009.
Celotna bibliografija je dostopna na SICRIS: http://sicris.izum.si/search/rsr.aspx?lang=slv&,id=5520