Studying the complexity of global verification for NP-hard discrete optimization problems

DOI10.1023/A:1024680908847zbMath1035.90112OpenAlexW1498470506MaRDI QIDQ1402543

Derek E. Armstrong, Jacobson, Sheldon H.

Publication date: 28 August 2003

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1024680908847

zbMATH Keywords

computational complexityNP-hardlocal search algorithmsdiscrete optimization problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

Analyzing the complexity of finding good neighborhood functions for local search algorithms ⋮ An analysis of neighborhood functions on generic solution spaces ⋮ Parameterized certificate dispersal and its variants

This page was built for publication: Studying the complexity of global verification for NP-hard discrete optimization problems