■
Team
■
Teaching
Information for students of B.Sc./M.Sc. Mathematics
Summer 2021
■
Winter 2020
Summer 2020
■
Winter 2019
■
Summer 2019
■
Winter 2018
■
Summer 2018
■
Winter 2017
■
Summer 2017
■
Winter 2016
■
Summer 2016
■
Winter 2015
■
Summer 2015
■
Winter 2014
■
Summer 2014
■
Winter 2013
Discrete Optimization
Erg. zu Algorithmen, Berechenbarkeit & Komplexität
Ergänzungen zu Logik & DS
■
Summer 2013
■
Winter 2012
■
Summer 2012
■
Winter 2011
Former Semester
BSc, Master-, Student-, Diplomathesis
StuPro/ ProjektINF/ SoPra/ FaPra
■
Research
Publications
Projects
Student Projects
 

Diskrete Optimierung/Discrete Optimization

Prof. Dr. Stefan Funke

This lecture takes place twice a week (3 h of lecture and 1 h tutorial) in the following slots:

Day Time Location
Tuesday 11:55-13:25 V38.02
Thursday 09:50-11:20 V38.02

Lecture starts on Tuesday, October 15th. Note the slight shift from the standard slots!

The first MC Test takes place on Tuesday, Dec 17th 12:00-13:00.

The second MC Test takes place on Tuesday, Feb 4th, 12:00-13:00, V38.02

The third MC Test takes place on Thu, Feb 27th, 10:00-11:00 in V38.02 (only if you have passed exactly one of the previous MC Tests).

There will be a Q&A session on Thu, Feb 27th, 11:00-12:00, V38.02, following the MC-test.

The exam takes place March, 5th, 11-13; see the Prüfungsamt for up-to-date information!

We will try to have the exam in the summer turm in September (will be set by the Prüfungsamt)

 

Introductory Slides

Lecture notes (in LaTeX, you can add your own notes, but have to ‘TeX’ it afterwards) as of 17.02.2014 (some corrections incorporated).

Fake MC-Test (to be discussed Dec 12th).

Results of the MC-Test ( >=55% were required to pass the test ).

Results of the 2nd MC-Test ( >=55% were required to pass the test – this is äquivalent to at most 10 wrong answers ).
06.02.2014: Two more candidates passed because the f-question had in fact two correct answers and these candidates ticked the other correct answers (as discussed in the lecture today).

Results of the 3rd MC-Test (>=55% were required to pass the test )

The additional 4th MC-Test will be on Sept 17th 2014 at 11:00 in V38.04.

The results of the 2nd DO exam from Sept 29th are published on the FMI dashboard (close to room 1.101).

Exclusions for the Exam

In general, all topics covered in class or tutorials are relevant for the exam
with the following exclusions:

  • randomized LP rounding for the Set Cover problem
  • Primal-Dual algorithm for the Uncapacitated Facility Location problem
  • local search algorithm for the Uncapacitated Facility Location problem

Possible topics covered in the course

  • Linear Programming
    • Simplex algorithm
    • Duality
    • Linear Programming in fixed dimensions, subexponential Simplex variants
  • Network Flow
    • MaxFlow/MinCut theorem
    • MinCostFlow
  • Approximation Algorithms for NP-hard problems
    • Knapsack, TSP, Set Cover, Hitting Set, …
    • Primal-Dual algorithms
    • Greedy and Dual-Fitting

There will be a written exam at the end of the semester (unless your Prüfungsordnung does not allow that; in that case, there will be an oral exam).

Exercises/Tutorials

not available anymore

Literature

A very good book on approximation algorithms by Shmoys and Williamson can be found online.

Intended Audience

Students at the master (INF, SWT, INFOTECH, Winfo, …) or advanced Bachelor level.

News

[Oct’21] We have migrated to our new webssite here!

[Jun’19] Our paper on trajectory storage and retrieval has been accepted at SSTD 2019!

[Nov’18] Our paper on regret minimization has been accepted at AAAI 2019 (acceptance rate 16.2%)!

[Oct’18] Our paper on alternative route planning for bicycles has been accepted at ALENEX 2019!

[Apr’18] Martin has successfully defended his Ph.D. thesis. Congratulations!

[Jan’18] The journal version of our paper on k-hop path covers will receive a publication award from our university!

[Nov’17] Our paper on a theoretical explanation for several speed-up techniques for route computation has been accepted at AAAI 2018!

[Oct’17] Thomas’ paper on area preserving map simplification has been accepted at ALENEX 2018!

[May’17] Daniel’s and Martin’s paper on rational points on the unit sphere has been accepted at ISSAC 2017!

[Apr’17] Our paper on personalized route planning with dynamic approximation guarantees has been accepted at SEA 2017!

[Jan’17] Martin’s paper on map matching has been accepted at SIAM SDM 2017!

[Nov’16] Our paper on simultaneous maze solving has been accepted at AAAI 2017.

[Okt’16] Two papers, one on growing balls (!), the other on map simplification will be presented at ALENEX 2017.

[Sep’16] Our paper on Deducing Individual Driving Preferences has been accepted at the 24th ACM SIGSPATIAL GIS 2016.

[Feb’16] Our paper on placing loading stations for EVs has been accepted at ICAPS 2016.

[Jul’15] Paper about our GeoSearch Engine OSCAR at the 16th Int. Conf on Web Information Systems Engineering (WISE)!

[Jun’15] We feel very honored to have our VLDB’14 paper almost verbatimly reproduced in the ‘prestigous’ journal IJSETR, see here. Yeah! 😉

[Feb’15] We were lucky to receive a Google Research Award for research on personalized route planning!

[Sep’14] Our paper “On k-Path Covers and their Applications” has received a Best Paper Award at the 40th Int. Conference on Very Large Databases (VLDB) in Hangzhou (5 out of 139 accepted out of 695 submitted papers).

[Sep’14] Our paper on “Energy-efficient Routing: Taking Speed into Account” has received a Best Paper Award at the 37th German Conference on Artificial Intelligence (KI).

[Jul’14] Our paper “Placement of Loading Stations for Electric Vehicles: No Detours Necessary!” has received a Honorable Mention at the 28th AAAI Conference on Artificial Intelligence (AAAI) in Quebec City (5 nominated out of 398 accepted out of 1406 submitted papers).

[Mar’14] Our StuPro-Team has completed their great “SchulScheduler” project.

[Nov’13] Jochen has defended his PhD thesis and moved on to TomTom.

[Feb’13] Sabine has defended her PhD thesis (already in Dec’12) and received the INFOS award for best CS PhD thesis in 2012!

[Mar’12] Our paper Path Shapes - An Alternative Method for Map Matching and Fully Autonomous Self-Localization presented at GIS 2011 has received the Best Paper Award, also see the ACM SIGSPATIAL newsletter.