Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

Project Seminar: Algorithms Engineering for Distance Sensitive Oracles

MSc Seminar - Winter 2023

Description

Dealing with failures is an essential part of modern computing. Built in processes that deal with failures are an essential part of many computing environments, from massive storage devices, large scale parallel computation, and communication networks.In this projectseminar we study how to answer queries in the presence of failures in a network, where one assumes apriori a bound on the number of simultaneous failures. Such a bound is especially relevant in the context of independent failures where the probability of multiple failures decreases exponentially with the number of failures.
In particular, we consider distance and shortest path queries in the presence of edge failures for undirected weighted graphs. Our goal is to preprocess a graph G=(V,E) and produce some (hopefully small) data structure used to answer subsequent queries of the form (s,t,F), where F is a subset of at most f edges.
The answer to such a query is an approximation to the shortest path length between s and t in the graph G - F (which is the graph obtained by removing the edges of F from G). Moreover, one may desire to print out such a path. We call such a data structure an f-DSO (DSO = Distance Sensitivity Oracle). There are several parameters to be considered with respect to suggested f-DSOs.

  • The size of the data structure required.
  • The time needed to answer distance queries (s,t,F).
  • The approximation ratio (also known as the stretch), how close are our estimated distances to the actual distances?
  • The time required for the preprocessing phase.

There has been tramendous amount of theoretical work on f-DSOs for optimizing the above parameters, for example:
SODA 2017
SODA 2019
ICALP 2019
STOC 2020
MFCS 2021
ESA 2021
ITCS 2021
ICALP 2022
STOC 2023

However, there is very limited algorithm engineering research for implementing these algorithms and data-structures.
In this project seminar we will explore algorithm engineering aspects of implementing some of these data-structures and algorithms.

Organization

We meet for the first time on Friday, October 27 at 11:00 via Zoom. The link will be posted to the Moodle page of the course.

Vorlesungsteam

An dieser Veranstaltung sind folgende Personen beteiligt:

[Sarel Cohen]

Chair for Algorithm Engineering
Hasso Plattner Institute

Office: K-2.18
E-Mail: Sarel.Cohen(at)hpi.de

Prof. Dr. Tobias Friedrich


Chair for Algorithm Engineering

Hasso Plattner Institute
University of Potsdam
Prof.-Dr.-Helmert-Str. 2-3
14482 Potsdam
Germany

Office: K-2.15

Tel.: +49 331 5509-410
Fax: +49 331 5509-429

E-Mail: tobias.friedrich(at)hpi.uni-potsdam.de