3 papers
cs.DS2021
Robust Online Algorithms for Dynamic Choosing Problems
Sebastian Berndt, Kilian Grage, Klaus Jansen +2
Semi-online algorithms that are allowed to perform a bounded amount of repacking achieve guaranteed good worst-case behaviour in a more realistic setting. Most of the previous work…
cs.DS2020
The Edit Distance to -Subsequence Universality
Pamela Fleischmann, Maria Kosche, Tore Koß +2
A word is a subsequence of another word if can be obtained from by deleting some of its letters. The word with alph is called -subsequence universal i…
cs.FL2020
Efficiently Testing Simon's Congruence
Pawel Gawrychowski, Maria Kosche, Tore Koss +2
Simon's congruence is defined as follows: two words are -equivalent if they have the same set of subsequences of length at most . We propose an algorithm which…