4 papers
Transformer Heads Looking for Order
Jasper van Doornmalen, Alexander Kozachinskiy, Corinna Mathwieser +4
In this note, we show that the problem of checking, whether a sequence of bits is ordered, is not doable by 1-head 1-layer transformers but is doable by a 2-head 1-layer transforme…
Parameterized complexity of scheduling unit-time jobs with generalized precedence constraints
Christina Büsing, Maurice Draeger, Corinna Mathwieser
We study the parameterized complexity of scheduling unit-time jobs on parallel, identical machines under generalized precedence constraints for minimization of the makespan and the…
Minimum-Peak-Cost Flows Over Time
Mariia Anapolska, Emma Ahrens, Christina Büsing +5
When planning transportation whose operation requires non-consumable resources, the peak demand for allocated resources is often of higher interest than the duration of resource us…
Special Cases of the Minimum Spanning Tree Problem under Explorable Edge and Vertex Uncertainty
Corinna Mathwieser, Eranda Cela
This article studies the Minimum Spanning Tree Problem under Explorable Uncertainty as well as a related vertex uncertainty version of the problem. We particularly consider special…