Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

02.11.2022

Four Papers accepted at SODA, ALENEX and HPEC

The Algorithm Engineering group is proud to contribute a paper to the Symposium on Discrete Algorithms (SODA) which will take place on January 22 - 25, 2023 in Florence. The paper by Kirill Simonov who recently joined our group, presents the first fixed-parameter algorithm for the problem of finding an (s, t)-path that contains at least k different colors, in a vertex-colored graph. The algorithm coincidentally improves the state of the art for the fundamental problem of finding an (s, t)-path of length at least k. The result also extends to the setting where colors are replaced by an arbitrary representable matroid over the vertex set.

Two more papers were accepted at Symposium on Algorithm Engineering and Experiments (ALENEX) which will be colocated with SODA. For the first one, our bachelor project partnered with TomTom developed the new routing algorithm SKARF, a combination of the skeleton dimension and Arc-Flags. On large real-world road networks it yields a reduction of 30% to 40% over the original Arc-Flags algorithm. The second paper was written by some of our Master students in the seminar Inferring infection chains. In the paper, the students implemented a previously unimplemented algorithm by Gabow et al. for computing directed minimum spanning trees and evaluated it against other algorithms om real-world and random graphs.

Additionally, a paper was accepted at this years IEEE conference on High Performance and Embedded Computing (HPEC), taking place virtually on September 19 - 23, 2022. The scope of the conference comprises computing hardware, software, systems and applications where performance matters. In this work, the authors research fault-tolerant training of machine learning models such as KMeans and GMM. They show that checkpointing the models' states during training using the new persistent memory NVRAM achieve a checkpointing speedup of a factor between 10 and 75x for KMeans and over 3x for GMM against the current state-of-the-art checkpointing approaches.

 

  • Casel, Katrin; Dierking, Jessica; Dunker, Rebekka; Egbert, Julian; Fischbeck, Philipp; Friedrich, Tobias; Helms, Christian; Isaac, Davis; Khomutovskiy, Ivan; Krogmann, Simon; Lenzner, Pascal; Schöllkopf, Finn Applying Skeletons to Speed Up the Arc-Flags Routing AlgorithmSIAM Symposium on Algorithm Engineering and Experiments (ALENEX) 2023
     
  • Böther, Maximilian; Kißig, Otto; Weyand, Christopher Efficiently Computing Directed Minimum Spanning TreesSIAM Symposium on Algorithm Engineering and Experiments (ALENEX) 2023
     
  • Towards Fast Crash-Consis... - Download
    Wood, Andrew; Hershcovitch, Moshik; Ennmouri, Ilias; Zong, Weiyu; Chennuri, Saurav; Cohen, Sarel; Sundararaman, Swaminathan; Waddington, Daniel; Chin, Peter Towards Fast Crash-Consistent Cluster CheckpointingHigh Performance Extreme Computing Conference (HPEC) 2022