Showing cs.CCShow all
2 papers · 1 filter
cs.CC2025
PLS-complete problems with lexicographic cost functions: Max--SAT and Abelian Permutation Orbit Minimization
Dominik Scheder, Johannes Tantow
How hard is it to find a local optimum? If we are given a graph and want to find a locally maximal cut--meaning that the number of edges in the cut can't be improved by moving a si…
cs.CC2025
PLS-completeness of string permutations
Dominik Scheder, Johannes Tantow
Bitstrings can be permuted via permutations and compared via the lexicographic order. In this paper we study the complexity of finding a minimum of a bitstring via given permutatio…