VL am 29. Januar 2019 muss leider entfallen! Am 31.Januar 2019 findet eine Übung statt (insbes. Blatt 5; falls Zeit, auch Blatt 4 bearbeiten).

Organization

  • Lectures: Prof. Dr. Stefan Funke (Raum 1.111)
  • Tutorials: Daniel Bahrdt, Florian Barth, Filip Krumpe, Thomas Mendel, Tobias Rupp

Time and Location of Lectures/Tutorials:

Time Location Starting
Tue 14:00-15:30 0.457 16.10.18
Thu **14:00-15:30** **1.140** 18.10.18

Execise Sheets

Small Java program for visualizing line segments on an OSM map here.

OpenGL viewer for larger graphs here (unpack; mkdir build; cmake ../; make) with a sample file

stutt.gl.bz2 (view with ./simple -opengl3 -gf stutt.gl).

Individual Project

Every student has to implement one of the concepts covered in class. Current options are (to be extended):

  • CH construction (own implementation)
  • Hub Labels creation (for a given CH)
  • Transit Nodes (for a given CH)
  • Arc Flags + PHAST (for a given CH)

Scribe Notes

The lecture will be accompanied by scribe notes (current version here (updated 13.03.2019)). Hints for the exam (updated 13.03.2019)

Contents (tentative)

In Algorithmics, one is interested in developing and designing algorithms which can solve a given problem as efficient as possible. For a theoretical computer scientist, this normally means to settle the computational complexity of the problem (Computable? NP-hard? PSPACE-hard? in P, NP, co-NP?) and then search for algorithms which are provably efficient, that is, comping up with fixed bounds on the time and space consumption by a rigorous mathematical analysis. And the less the resource consumption, the better the algorithm. But for real-world problems, as e.g. coming up with the best tours for a fleet of mail delivery vehicles, the algorithm with the best theoretical runtime is not automatically the most suitable algorithm. Here, it is more important, that the algorithm is actually implementable, produces quick and good solutions for the relevant instances and is flexible in case something new has to be considered. The scope of Algorithm Engineering is to design algorithms which work in both worlds. So we still aim for theoretical performance (and solution quality) guarantees, but equally important is the actual performance of the algorithm on real-world data, which makes implementation and evaluation mandatory. Note that AE is not the same as heuristic problem solving, where often optimality or even completeness is compromised in order to get some fast solution. Heuristics are typically not thoroughly analyzed but their validation is purely empirical. Topics will include amongst others:

  • Route Planning (e.g., how to answer queries in the mili- micro- or nanoseconds range instead of SECONDS via Dikstra
  • Information Retrieval (e.g., how to retrieve all movies that contain zombie and vampire in their short description)
  • (I)LP-based techniques – travelling salesperson, multicriteria shortest paths

Literatur

Manuscript about a theoretical analysis of speed-up techniques.

Survey about route planning in transportation networks.

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.