# Approximation Algorithms (MA5517)
lecture

An approximation algorithm for an optimization problem is an algorithm that runs in polynomial time in the size of the input and computes a solution that is guaranteed to be within a certain factor of the optimal solution. This course will cover general techniques for designing approximation algorithms such as greedy algorithms, LP rounding, and the primal-dual method. We will apply these techniques to derive algorithms for many fundamental combinatorial optimization problems such as the Steiner tree problem, the traveling salesman problem, or the set cover problem.
Lecturer: | Jannik Matuschke |
---|---|

Teaching assistant: | Marcus Kaiser |

Weekly hours: | 2+1 hours |

ECTS credits: | 5 |

News | Schedule | Lecture notes | Problem sets | Literature |

## News

- The course is over. Thanks everyone for your participation!

# Schedule

## Lectures

Day | Time | Room | Lecturer |
---|---|---|---|

Mon | 12:15-13:45 | 02.08.011 | Jannik Matuschke |

## Tutorial Classes

Day | Time | Room | Lecturer |
---|---|---|---|

Tue (biweekly) | 16:15-17:45 | MW Room 1237 (02.01.237) | Marcus Kaiser |

# Lecture notes/slides

- Lecture 1 (Oct 24, 2016): Introduction to Approximation Algorithms, Set Cover Problem: LP Rounding, Primal-dual Method, Greedy Algorithm. Suggested Reading: Chapter 1 of The Design of Approximation Algorithms. (slides) (notes)
- Lecture 2 (Oct 31, 2016): Set Cover Problem: Randomized LP Rounding, Combinatorial Lower Bounds, Hardness of Approximation; Combinatorial Lower Bounds for the Traveling Salesman Problem. Suggested Reading: Sections 1.7 & 2.4 of The Design of Approximation Algorithms. (slides) (notes)
- Lecture 3 (Nov 14, 2016): Greedy Algorithms and Local Search: Minimum Spanning Trees, Scheduling on Identical Parallel Machines, k-Center Problem. Suggested Reading: Sections 2.2 & 2.3 of The Design of Approximation Algorithms. (warm-up) (slides) (notes)
- Lecture 4 (Nov 21, 2016): Dynamic Programming and Rounding the Input Data: Knapsack, Scheduling on Identical Parallel Machines. Suggested Reading: Sections 3.1 & 3.2 of The Design of Approximation Algorithms. (slides) (notes)
- Lecture 5 (Nov 28, 2016): LP Rounding: Prize-collecting Steiner Tree and Uncapacitated Facility Location. Suggested Reading: Sections 4.3-4.5 & 5.7-5.8 of The Design of Approximation Algorithms. (slides) (notes)
- Lecture 6 (Dec 5, 2016): Random Sampling and Randomized LP Rounding: Uncapacitated Facility Location, Maximum Satisfiability. Suggested Reading: Sections 5.1-5.6 & 5.8 of The Design of Approximation Algorithms. (slides) (notes)
- Lecture 7 (Dec 12, 2016): LP Rounding for Max Sat; Chernoff Bounds: Integer Multicommodity Flows; Rounding Semidefinite Programs: MAX CUT. Suggested Reading: Sections 5.9-5.10 & Chapter 6 of The Design of Approximation Algorithms. (slides) (notes)
- Lecture 8 (Dec 19, 2016): The Primal-Dual Method: The Shortest Path Problem & The Generalized Steiner Tree Problem. Suggested Reading: Sections 7.1-7.4 of The Design of Approximation Algorithms. (slides) (notes)
- Lecture 9 (Jan 16, 2017): Primal-dual Method for Uncapacitated Facility Location, Lagrangean Relaxation for the k-Median Problem. Suggested Reading: Sections 7.6 & 7.7 of The Design of Approximation Algorithms. (slides) (notes)
- Lecture 10 (Jan 23, 2017): Iterated Rounding for Survivable Network Design. Suggested Reading: Section 11.3 of The Design of Approximation Algorithms. (slides) (notes)
- Lecture 11 (Jan 24, 2017): Randomized Iterated Rounding for Steiner Tree. Suggested Reading: Section 12.3 of The Design of Approximation Algorithms. (slides) (notes)
- Lecture 12 (Jan 30, 2017): Tree Metrics and Buy-At-Bulk Network Design. Suggested Reading: Section 8.5-8.6 of The Design of Approximation Algorithms. (slides) (notes)
- Lecture 13 (Feb 6, 2017): Combining Multiple Approximation Algorithms: Location Routing. Suggested Reading: Section 4.1-4.2 of Network flows and network design in theory and practice
^{}. (slides) (notes)

- Q & A Session at MW Room 1237 (02.01.237) (Feb 7, 2017)

# Problem sets

- Problem Set 1: Applying Results on the Approximability of the Set Cover Problem (Discussion: Nov 8, 2016; solution sketch)
- Problem Set 2: Greedy Algorithms and Combinatorial Bounds (Discussion: Nov 22, 2016; solution sketch)
- Problem Set 3: Relaxed Decision Procedures and an FPTAS (Discussion: Dec 06, 2016; solution sketch)
- Problem Set 4: Rounding and Randomized Algorithms (Discussion: Dec 20, 2016; solution sketch)
- Problem Set 5: Semidefinite Programming and the Primal-Dual Method (Discussion: Jan 17, 2017; solution sketch)
- Problem Set 6: More on the Primal-Dual Method and Iterated Rounding (Discussion: Jan 31, 2017; solution sketch)

## Coding Challenge

Updates:- Representation of floating point numbers in decimal system
- Change of the type of coordinate values from
`vector_float`

to`string`

- Adaption of the exemplary code

^{}, plot.py

^{}Deadline: tbd (February 2017) Exemplary instances:

Problem | Instances | Source | Description |
---|---|---|---|

Minimum Steiner Tree | X ^{} |
SteinLib Testdata Library ^{} |
Complete graphs with euclidian distances |

Minimum Steiner Tree | PUC ^{} |
SteinLib Testdata Library ^{} |
Hypercubes |

Minimum Steiner Tree | Vienna ^{} |
University of Vienna ^{} |
Real-world examples of telecommunication networks |

Generalized Steiner Tree | X ^{} |
SteinLib Testdata Library ^{} |
As above with random terminal pairs |

Generalized Steiner Tree | PUC ^{} |
SteinLib Testdata Library ^{} |
As above with random terminal pairs |

Generalized Steiner Tree | Vienna ^{} |
University of Vienna ^{} |
As above with random terminal pairs |

Prize-collecting Steiner Tree | Cologne ^{} |
University of Vienna ^{} |
Real-world instances used in the design of fiber optic networks |

Prize-collecting Steiner Tree | H ^{} |
DIMACS ^{} |
Hypercubes with random root |

# Literature

The course will be based on the book- David P. Williamson, David B. Shmoys, The Design of Approximation Algorithms
^{}, Cambridge University Press, 2011.

- G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer Verlag, 1999
- D. S. Hochbaum (ed.), Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, 1995
- B. Korte, J. Vygen, Combinatorial Optimization, Springer Verlag, 5th edition, 2012
- M. Mitzenmacher, E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, 2005
- V. V. Vazirani, Approximation Algorithms, Springer Verlag, 2001