An alternative approach for proving the NP-hardness of optimization problems

DOI10.1016/j.ejor.2015.06.076zbMath1346.90833MaRDI QIDQ320621

Mohammad Hasan, M. Dambrine

Publication date: 7 October 2016

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2015.06.076

zbMATH Keywords

computational complexity; scheduling; combinatorial optimization

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90B35: Deterministic scheduling theory in operations research

90C27: Combinatorial optimization

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)