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

Edwin Tai Chiu Cheng; Y. Shafransky; Chi To Ng

doi:10.1016/j.ejor.2015.06.076

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

Research output: Journal article publication › Journal article › Academic research › peer-review

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 language	English
Pages (from-to)	52-58
Number of pages	7
Journal	European Journal of Operational Research
Volume	248
Issue number	1
DOIs	https://doi.org/10.1016/j.ejor.2015.06.076
Publication status	Published - 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

More information

10.1016/j.ejor.2015.06.076

Cite this

@article{c13f95ea4e7d49aa9272b3d6b89f571c,

title = "An alternative approach for proving the NP-hardness of optimization problems",

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.",

keywords = "Combinatorial optimization, Computational complexity, Scheduling",

author = "Cheng, \{Edwin Tai Chiu\} and Y. Shafransky and Ng, \{Chi To\}",

year = "2016",

month = jan,

day = "1",

doi = "10.1016/j.ejor.2015.06.076",

language = "English",

volume = "248",

pages = "52--58",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

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

AU - Cheng, Edwin Tai Chiu

AU - Shafransky, Y.

AU - Ng, Chi To

PY - 2016/1/1

Y1 - 2016/1/1

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

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

KW - Combinatorial optimization

KW - Computational complexity

KW - Scheduling

UR - https://www.scopus.com/pages/publications/84940893546

U2 - 10.1016/j.ejor.2015.06.076

DO - 10.1016/j.ejor.2015.06.076

M3 - Journal article

SN - 0377-2217

VL - 248

SP - 52

EP - 58

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 1

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this