On the hardness of losing weight

DOI10.1145/2151171.2151182zbMath1295.68123OpenAlexW2008809414MaRDI QIDQ3189060

Dániel Marx, Andrei A. Krokhin

Publication date: 9 September 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2151171.2151182

zbMATH Keywords

complexitylocal searchconstraint satisfaction problemfixed-parameter tractability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

The parameterized complexity of local search for TSP, more refined ⋮ On the complexity of restoring corrupted colorings ⋮ Local search for string problems: brute-force is essentially optimal ⋮ Searching for better fill-in ⋮ On the parameterized complexity of consensus clustering ⋮ Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction

This page was built for publication: On the hardness of losing weight