3 papers
cs.DS2026
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…
cs.DS2025
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…
cs.DS2024
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…