کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
479457 1445993 2016 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An alternative approach for proving the NP-hardness of optimization problems
ترجمه فارسی عنوان
یک روش جایگزین برای اثبات NP-سختی مسائل بهینه سازی
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی


• 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 248, Issue 1, 1 January 2016, Pages 52–58
نویسندگان
, , ,