In “Height-bounded Lempel-Ziv Encodings”, Professor Simon Puglisi and colleagues from Tokyo Medical and Dental University (now Science Tokyo) and NTT Communications Japan, describe a new family of compressed data representations - height-bounded Lempel-Ziv encoding - that allows arbitrary parts of the compressed data to be extracted rapidly. The approach can be computed efficiently and has strong theoretical bounds on extraction time. Moreover, prototype implementations described in the paper seem to be efficient in practice. This work was presented at the 36th European Symposium on Algorithms (ESA 2024) in London, where it received the Best Paper Award for the Algorithm Engineering and Experimental Analysis track.
In “Accelerating ILP solvers for Minimum Flow Decompositions through search space and dimensionality reductions”, Doctoral Researcher Andreas Grigorjew, Associate Professor Alexandru Tomescu and colleagues from Aalto University, Finland, and University of Verona, Italy, speed-up solvers for the Minimum Flow Decomposition problem by 30-200 times on the hardest instances. This problem asks for a minimum set of weighted paths whose superposition equals a given network flow, and has applications in several computer science, fields including bioinformatics, networking and transportation. This work was presented at the 22nd International Symposium on Experimental Algorithms (SEA 2024) in Vienna, where it obtained the Runner-Up to the Best Paper award.