# Randomized and Approximation Algorithms

## Advanced Course, 2+2

# Basic Information

Given by: | Antonios Antoniadis and Marvin Künnemann |
---|---|

Time: | Tuesday, 14:00- 16:00 |

Exercises by: | André Nusser |

Exercises | Thursday, 14:00-16:00 |

Room: | 024 E1.4 |

First Meeting: | October 16th. |

Credits: | 6 credit points |

Grade formula: | The grade is fully determined by the exam (depending on number of participants, either oral or written). To qualify for the exam, 50 % points in the exercise sheets are required. |

Prerequisites: | You will need to be mathematically mature. You should be able to read and understand technical/mathematical texts, and should have basic knowledge in Algorithms and Probability Theory. |

# News

- The
**oral exam**will take place on February 27th between 10:15 and 15:10 in room 309a (building E1.4). In case you have not yet received an e-mail with your exact slot, please contact us as soon as possible. **Room Change on Jan 15**: Lecture will take place in**Room 023**!**Tentative date for oral exam:**27.2.2019, 14:00.- The
**project**is now online: Average-Case Analysis of Orthogonal Vectors - The exercise session on December 20th will not take place.
- Again, a typo was spotted! In the return statement in
**Exercise 2 on Sheet 5**, it should have been "max" instead of "min". - In Exercise 4 on Sheet 2, there was a typo: the edge weights are natural numbers (in particular, non-negative)

# Description

Several practically relevant algorithmic problems are unfortunately not known to have deterministic efficient algorithms. More specifically, for several important problems, it is highly unlikely that an efficient algorithm exists that produces an optimal solution on every input instance. Since often such problems are too important to be left unadressed, there are several "relaxations" being used to adress such problems. Two of them are:

**Approximation Algorithms:**One can relax the objective of searching for the optimal solution and instead design an efficient algorithm that produces solutions which are provably "close" in value to the optimal one.**Randomized Algorithms, and Probabilistic Analysis of Algorithms:**Often, allowing an algorithm to make random choices during its execution leads to significantly more efficient computation (possibly with the drawback that the efficiency is only guaranteed with some probability, or that the output is correct only with some probability). Especially in the context of approximation algorithms, such randomized methods provide powerful tools. Furthermore, many problems are known to be difficult only in specific, pathetic instances whereas for instances apearing in practice efficient algorithms may exist. Probabilistic analysis of algorithms can, in many cases, give a theoretical explanation of this phenomenon.

In this course we will focus on several techniques for designing and analyzing randomized and approximation algorithms. We will also see a couple of interesting recent results in the area.

# Schedule

Date | Speaker | Topic | Reference | Exercise Sheet |
---|---|---|---|---|

Oct 16 | Antonios & Marvin | Introduction to the Course. Introduction to Approximation Algorithms. Greedy Algorithms | W&S: Subsect. 1.1, 1.2 (first part), 1.6 (first part), 2.1, 2.2. | Exercise Sheet 1 |

Oct 23 | Marvin | Introduction to Randomized Algorithms. Basics in probaility theory, Freivalds' algorithm, Max-3SAT. | M&U: Chapters 1+2. | |

Oct 30 | Antonios | Local Search | W&S: Subsect. 2.3, 2.6. | Exercise Sheet 3 |

Nov 6 | Antonios | Dynamic Programming. Knapsack. (Fully) Polynomial Time Approximation Schemes. | W&S: Subsect. 3.1, Ideas from 3.2. | Exercise Sheet 4 |

Nov 13 | Marvin | Concentration I: Chebychev and Applications (Hashing, Counting Distinct Items in Streams) | M&U: Chapter 3. Chapter 2 of Data Stream Algorithms Lecture Notes | Exercise Sheet 5 |

Nov 20 | Antonios | Linear Programming, Deterministic Rounding. | W&S: 1.3, Ideas from 4.5 | Exercise Sheet 6 |

Nov 27 | Marvin | Concentration II: Chernoff Bounds and Applications. | M&U: Chapter 4. | |

Dec 4 | Marvin | Linear Programming, Randomized Rounding: Minimum-capacity multicommodity flow, MAX SAT. | W&S: Subsect. 5.11, 5.4, 5.6. | |

Dec 11 | Antonios | Linear Programming, Primal-Dual Algorithms I | W&S: Subsect, 1.4,1.5, Appendix A, 7.1, 7.3 & 7.6 | Exercise Sheet 9 |

Dec 18 | Antonios | Linear Programming, Primal Dual Algorithms II | - see above - | Exercise Sheet 10 |

Jan 8 | - | No Lecture: Project | ||

Jan 15 | Marvin | Derandomization (Room Change to 023!) | W&S: Subsect, 5.2, M&U: 13.1.2 | Exercise Sheet 11 |

Jan 22 | Marvin | Hardness of Approximation | V. Vazirani: "Approximation Algorithms", Chapter 29 | Exercise Sheet 12 |

Jan 29 | Antonios | The Geometry of Scheduling | The Geometry of Scheduling | --- |

Feb 5 | Marvin | Approximation in the Polynomial-Time Regime |

# Bibliography

- D.P. Williamson, D.B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011.
- M. Mitzenmacher, E. Upfal. Probability and Computing. Cambridge University Press, 2005.