Establishes PLS-completeness for lexicographic local search in 4-CNF and 3-CNF (double flips), and for Abelian permutation orbit minimization even when groups are cyclic or consist of involutions, with applications to bounded congestion games.
Integer linear programs and local search for max-cut
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
fields
cs.CC 2representative citing papers
The paper gives tight ETH-based lower bounds and matching algorithms for Minimum Stable Cut parameterized by treewidth and degree, plus an FPT approximation scheme for almost-stable cuts.
citing papers explorer
-
PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
Establishes PLS-completeness for lexicographic local search in 4-CNF and 3-CNF (double flips), and for Abelian permutation orbit minimization even when groups are cyclic or consist of involutions, with applications to bounded congestion games.
-
Minimum Stable Cut and Treewidth
The paper gives tight ETH-based lower bounds and matching algorithms for Minimum Stable Cut parameterized by treewidth and degree, plus an FPT approximation scheme for almost-stable cuts.