TUM – TUM – Menü

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)

Outlook

Problem sets

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

Description: The Minimum Steiner Tree Problem and its Variants

Code files: parse.py , 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

You can find additional instances to test against by following the links in the source column.

Literature

The course will be based on the book

Further reading:
  • 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

Research Unit M9


Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
Germany
phone:+49 89 289-16858
fax:+49 089 289-16859
sekretariat-m9ma.tum.de

Professors

Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Stefan Weltge
Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

News

April 2018
Case Studies 2018: Save the date: Case Studies poster presentation on May 25th, 2018, final workshop on July 7th, 2018.