Please use this identifier to cite or link to this item:
Title: An alternative approach for proving the NP-hardness of optimization problems
Authors: Cheng, TCE 
Shafransky, Y
Ng, CT 
Keywords: Combinatorial optimization
Computational complexity
Issue Date: 2015
Publisher: Elsevier
Source: European journal of operational research, 2015 How to cite?
Journal: European journal of operational research 
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.
ISSN: 0377-2217
EISSN: 1872-6860
DOI: 10.1016/j.ejor.2015.06.076
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

Last Week
Last month
Checked on Aug 13, 2017

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.