کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
479457 | 1445993 | 2016 | 7 صفحه PDF | دانلود رایگان |
• A new approach for proving the NP-hardness of optimization problems is proposed.
• The new approach includes the “classical” approach as a special case.
• NP-hardness of a problem is proved, for which the classical approach is not applicable.
• Polynomially solvable problem with NP-hard computable objective is formulated.
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.
Journal: European Journal of Operational Research - Volume 248, Issue 1, 1 January 2016, Pages 52–58