6 papers
Pack, Remove, Reserve -- Online Knapsack with Second Thoughts
Hans-Joachim Böckenhauer, Dennis Komm, Emanuel Skodinis +2
We study the online proportional knapsack problem with two paid forms of recourse. Items arrive one by one and must be handled immediately, without knowledge of the future: an algo…
Tokenisation over Bounded Alphabets is Hard
Violeta Kastreva, Philip Whittington, Dennis Komm +1
Recent works have shown that tokenisation is NP-complete. However, these works assume tokenisation is applied to inputs with unboundedly large alphabets -- an unrealistic assumptio…
Traffic-Oblivious Multi-Commodity Flow Network Design
Markus Chimani, Max Ilsen
We consider the Minimum Multi-Commodity Flow Subgraph (MMCFS) problem: given a directed graph with edge capacities and a retention ratio , find an edg…
Tokenisation is NP-Complete
Philip Whittington, Gregor Bachmann, Tiago Pimentel
In this work, we prove the NP-completeness of two variants of tokenisation, defined as the problem of compressing a dataset to at most symbols by either finding a vocabulary di…
Online String Attractors
Philip Whittington
In today's data-centric world, fast and effective compression of data is paramount. To measure success towards the second goal, Kempa and Prezza [STOC2018] introduce the string att…
The 2-Attractor Problem is NP-Complete
Janosch Fuchs, Philip Whittington
A -attractor is a combinatorial object unifying dictionary-based compression. It allows to compare the repetitiveness measures of different dictionary compressors such as Lempel…