Exact Algorithms via Monotone Local Search

DOI10.1145/3284176zbMath1427.68119arXiv1512.01621WikidataQ60488372 ScholiaQ60488372MaRDI QIDQ5244381

Serge Gaspers, Fedor V. Fomin, Saket Saurabh, Daniel Lokshtanov

Publication date: 21 November 2019

Published in: Journal of the ACM, Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1512.01621

zbMATH Keywords

local search; satisfiability; randomized algorithms; parameterized algorithms; exact exponential algorithm; parameterized algorithm; subset problems; combinatorial bounds; exponential time algorithms

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

68W05: Nonnumerical algorithms

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68W20: Randomized algorithms