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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

6 Citations (Scopus)

Abstract

We provide a new reduction-based approach for proving the NP-hardness of optimization problems and establish that it includes the "classical" approach as a special case. We apply our alternative approach to prove the NP-hardness of a problem for which the classical approach is not applicable. Besides, we construct a special case of the problem with the property that finding an optimal element takes polynomial time despite that computing the objective function values is NP-hard.
Original languageEnglish
Pages (from-to)52-58
Number of pages7
JournalEuropean Journal of Operational Research
Volume248
Issue number1
DOIs
Publication statusPublished - 1 Jan 2016

Keywords

  • Combinatorial optimization
  • Computational complexity
  • Scheduling

ASJC Scopus subject areas

  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Cite this