Project Idea: Shortest Paths hos Københavns Universitet

Algorithms and Complexity

Forskerne prøver at forstå hvordan computere effektiv kan løse kombinatoriske problemer. For det meste arbejder forskerne teoretisk med hjælp fra matematikken. Desuden har de en stærk indflydelse på den virkelige verden, såsom at løse problemer inden for machine learning.

Forskning-sektionen er inddelt i tre områder:

  • Basic Algorithms

  • Big Data Analytics

  • Dynamic and Static Graph Algorithms and Data Structures

Læs mere her: https://di.ku.dk/english/research/ac/

 

ENGELSK VERSION:

The researchers try to understand how efficiently computers can solve combinatorial problems. Most of the work is theoretical using the power of mathematics, yet they have a strong track record of impact on the real world, e.g., focusing on problems recurring in machine learning.

The section is divided into three areas:

  • Basic Algorithms

  • Big Data Analytics

  • Dynamic and Static Graph Algorithms and Data Structures

Read more here: https://di.ku.dk/english/research/ac/

 

Background
Shortest paths is a classical problem in computer science which has found numerous practical
applications. Real-life networks such as road maps are often of considerable size and efficient
algorithms and data structures are needed for solving the shortest path problem on these networks.
Even an algorithm like Dijkstra which runs in near-linear time is often too slow in practice as it may explore a large part of the graph to find a shortest path between a single vertex
pair. An algorithm like A* is often much faster when provided with a good heuristic for estimating shortest path distances. Another variant which often beats Dijkstra in practice is
bidirectional search.
Even better time bounds can be obtained if we allow preprocessing the input graph and building a data structure on top of it. One extreme example is a giant look-up table which for
each vertex pair (u, v) stores a shortest path from u to v (or just the distance between them).
This allows for very fast running time but the drawback is obviously the large space requirement. If we do not require the paths output to be shortest but allow some approximation (for instance, the weight of the path output is required to be within 1% of the shortest one) then
data structures are known which offer tradeoffs between time, space, and approximation.

Project description

  • Make a survey on the litterature of shortest paths.
  • Implement various (exact and/or approximate) shortest path algorithms and data structures
  • Experimentally test the performance of these on suitable graph instances
  • Performance measures may include running time, space requirement, quality of solution
    found (in case of approximate shortest paths)
  • Compare the results of these experiments with the theoretical bounds to see how they
    match up

Supervision
Jacob Holm, assistant professor. Responsible for coordination of AC bachelor projects.
Actual supervisor TBD. jaho@di.ku.dk

Husk at nævne, at du fandt dette opslag på KU Projekt & Job