Prof. Dr. Stefan Funke

Schedule

Due to the Corona situation, the lecture will be offered in an online format only.

Video clips with lectures and tutorials will be uploaded to the ILIAS course around the same time, regular lectures/tutorials would have taken place (Tue 1130-1300, Thu 0945-1115).

Further information about live question and answer sessions will be posted soon within the ILIAS course.

The official way of communication is the ILIAS course.

NOTE A first Q&A session will be on November, 5th, 2020, 10:15-11:15 via Jitsi. The main purpose of this meeting is to identify technical difficulties that could be fixed in subsequent meetings. If you have no access to ILIAS, please ask for the link via EMail to the lecturer.

If you are student in Hohenheim, you might require a special link for joining the ILIAS course. Please contact Petra van Schayck.

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).

Literature

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

Lecture Notes (currently work in progress. Please report any mistakes if you find some).

Videos

NOTE The list of videos below is not maintained any longer. New videos will be uploaded to the Ilias course only. Please contact Petra van Schayck if you can’t access the Ilias course.

week 1: Intro to Max Flow

week 1: Intro to Max Flow - Recap

week 1: Max Flow: Towards a solution

week 1: Max Flow: Ford-Fulkerson

week 1: Max Flow: Termination and Correctness

week 2: Max Flow: Running Time and Capacity Scaling

week 2: Max Flow: Edmonds-Karp Algorithm

Tutorial

NOTE The material list for the tutorial below is not maintained any longer. New material will be uploaded to the Ilias course only. Please contact Petra van Schayck if you can’t access the Ilias course.

Exercise sheet 1

Solutions sheet 1

Solution video sheet 1 exercise 1

Solution video sheet 1 exercise 2

Solution video sheet 1 exercise 3

Solution video sheet 1 exercise 4

Solution video sheet 1 exercise 5

Basic Concepts

should be easy to find via google, e.g.

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!

All news

[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.

[Feb’12] Our group was awarded a Google Focused Grant on Mathematical Optimization and Combinatorial Optimization in Europe!