From the 1 of 4 linked papers with an AI index.
4 papers
Pack, Remove, Reserve -- Online Knapsack with Second Thoughts
Hans-Joachim Böckenhauer, Dennis Komm, Emanuel Skodinis +2
The paper analyzes the online proportional knapsack problem when both reservation and removal actions are allowed, determining optimal competitive ratios for all cost parameter pai…
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 ed…
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 d…