There are no prerequisites.

# Approximation and randomized algorithms

Borut Robič

Borut Robič

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