On the Hardness of Losing Weight
From MaRDI portal
Publication:3521957
DOI10.1007/978-3-540-70575-8_54zbMath1153.68382arXiv1711.03894MaRDI QIDQ3521957
Dániel Marx, Andrei A. Krokhin
Publication date: 28 August 2008
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1711.03894
68Q25: Analysis of algorithms and problem complexity
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Local search: is brute-force avoidable?, Stable assignment with couples: parameterized complexity and local search, The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT, Parameterized complexity and local search approaches for the stable marriage problem with ties, Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight, Constraint Satisfaction Parameterized by Solution Size, The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT