Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

31.07.2020

Two papers accepted at ATMOS and WAOA

The ALGO 2020 Meeting combines the European Symposium on Algorithms (ESA) and a number of other specialized conferences and workshops. It will be held on September 7-10 co-organized by the University of Pisa. As one of those, the Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) is an international forum for researchers in the area of optimization methods and algorithms to facilitate planning and operational management of freight and passenger transportation and traffic. To this year's edition, we contribute a paper resulting from a close collaboration between the Algorithm Engineering Group and TomTom. The paper is the result of the 2020 Bachelor Project where we introduce a framework to formalize real-world strategic routing scenarios as algorithmic problems and study one of them in detail.

The Workshop on Approximation and Online Algorithms (WAOA), another part of the meeting, is an international workshop in the area of approximation and online algorithms. These are fundamental tools to deal with computationally hard problems and problems in which the input is gradually disclosed over time. The Algorithm Engineering group contributes one paper to this year's edition. This paper is the results of the Master Thesis of Ardalan Khazraei. It shows that the uniform cost-distance Steiner tree problem remains NP-hard even if all vertices are terminals rendering the Steiner tree into a spanning tree, and improves the constant factor approximation.

  • A Strategic Routing Frame... - Download
    Bläsius, Thomas; Böther, Maximilian; Fischbeck, Philipp; Friedrich, Tobias; Gries, Alina; Hüffner, Falk; Kißig, Otto; Lenzner, Pascal; Molitor, Louise; Schiller, Leon; Wells, Armin; Wietheger, Simon A Strategic Routing Framework and Algorithms for Computing Alternative PathsAlgorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) 2020: 10:1–10:14
     
  • Held, Stephan; Khazraei, Ardalan An Improved Approximation Algorithm for the Uniform Cost-Distance Steiner Tree ProblemWorkshop on Approximation and Online Algorithms (WAOA) 2020: 189–203