Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/28798
Title: An alternative approach for proving the NP-hardness of optimization problems
Authors: Cheng, TCE 
Shafransky, Y
Ng, CT 
Keywords: Combinatorial optimization
Computational complexity
Scheduling
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.
URI: http://hdl.handle.net/10397/28798
ISSN: 0377-2217
EISSN: 1872-6860
DOI: 10.1016/j.ejor.2015.06.076
Appears in Collections:Journal/Magazine Article

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

Page view(s)

112
Last Week
1
Last month
Checked on Aug 13, 2017

Google ScholarTM

Check

Altmetric



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