A large number of problems arising in practical scenarios like communication, transportation, planning, logistics etc. can be modeled as combinatorial optimization problems. In most cases, these problems are computationally intractable and one often resorts to heuristics that provide sufficiently good solutions in reasonable amount of runtime. However, in most cases, such heuristics do not provide a worst case guarantee on the performance in comparison to the optimum solution. In this course, we shall study algorithms for combinatorial optimization problems which can provide strong mathematical guarantees on performance. The course aims at developing a toolkit for solving such problems. The lectures will consist of designing polynomial time algorithms and proving bounds on their worst case performances.

Lecturers: |
Dr. Ruben Hoeksma (Email) Prof. Dr. Nicole Megow (Email) |
---|---|

Time & Room: |
Mon 14-16 in room MZH 1090 Thu 10-12 Uhr in room MZH 1110 |

Start: |
Thursday, April 5, 2018 |

- [WS] The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys online version
- [V] Approximation Algorithms, Vijay V. Vazirani online version

Date | Topic | Material & suggested reading | Exercises |
---|---|---|---|

05/04/18 | Introduction, greedy algorithms: k-center problem and load balancing | slides, notes, Sections 2.2 & 2.3 of [WS] | -- |

09/04/18 | Greedy algorithms: scheduling with due dates, set cover problem | slides, notes, Sections 2.1 & 1.6 of [WS] | Exercise 1 |

12/04/18 | set cover (cont.), metric TSP (double tree and Christofides' Alg.), hardness of approximation for TSP (gap reduction) | slides, Section 2.4 of [WS] | -- |

19/04/18 | local search, load balancing, k-median | slides, notes, Section 2.3 and 9.2 of [WS] | -- |

23/04/18 | PTASs, bin packing, load balancing | slides, notes, Section 3.1 and 3.2 and Appendix B of [WS] | -- |

26/04/18 | PTAS for ETSP | notes, Section 10.1 of [WS] | Exercise 2 |

07/05/18 | Linear programming and rounding, scheduling with release dates | slides, notes, Section 4.1 and 4.2 of [WS] | Exercise 3 |

14/05/18 | LP rounding, Prize-collecting steiner treex | slides, notes, Section 4.3 and 4.4 of [WS] | -- |

17/05/18 | LP Duality, Exercise 3 | slides, Appendix A of [WS] | -- |

24/05/18 | Exercise 3, LP-rounding, uncapacitated facility location | slides, notes, Section 4.5 of [WS] | -- |

28/05/18 | Random sampling, Max SAT, Max CUT | notes, Section 5.1, 5.2 and 5.3 of [WS] | -- |

31/05/18 | Randomized rounding, the best of two algorithms, Max SAT | notes, Section 5.4, 5.5 and also 5.6 of [WS] | Exercise 4 |

04/06/18 | Scheduling by alpha-points, randomized alpha points, 1|r_j|sum (w_j)C_j | slides, article (slightly different algorithm formulation) | -- |

11/06/18 | LP Rounding, prize-collecting steiner tree, uncapacitated facility location, Chernoff bounds, multicommodity flow | slides, notes, Section 5.7, 5.8, 5.10, and 5.11 of [WS] | Exercise 5 |

14/06/18 | Primal-dual algorithms, set cover, shortest path, knapsack cover | slides, notes, Section 7.1, 7.3, and 7.5 of [WS] | -- |

18/06/18 | Primal-dual algorithms, uncapacitated facility location, prize-collecting steiner tree | slides, notes, Section 7.6 and 14.1 of [WS] | Exercise 6 |

Universität Bremen

FB3: Mathematik/Informatik

Bibliotheksstr.

28359 Bremen

Germany