On complexity of unconstrained hyperbolic 0-1 programming problems

被引：30

作者：

Prokopyev, OA

Huang, HX

Pardalos, PA ^{[1
]}

机构：

[1] Univ Florida, Ctr Appl Optimizat, Dept Ind & Syst Engn, Gainesville, FL 32611 USA

[2] Tsing Hua Univ, Dept Math Sci, Beijing 100084, Peoples R China

来源：

OPERATIONS RESEARCH LETTERS | 2005年 / 33卷 / 03期

基金：

中国国家自然科学基金; 美国国家科学基金会; 美国国家卫生研究院;

关键词：

hyperbolic; 0-1; programming; complexity; uniqueness; local search; approximability;

D O I：

10.1016/j.orl.2004.05.011

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Single- and multiple-ratio unconstrained hyperbolic 0-1 programming problems are considered. We prove that checking whether these problems have a unique solution is NP-hard. Furthermore, we show that finding the global maximizer of problems with unique solution remains NP-hard. We also discuss complexity of local search and approximability for multiple-ratio problems. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：312 / 318

页数：7

共 18 条

[1]

[Anonymous], P 23 ANN S FDN COMP

[2]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[3]

Arora S., 1996, Approximation Algorithms for NP-Hard Problems, P399

[4]

Arora S.R., 1977, INDIAN J PURE APPL M, V8, P578

[5]

Bellare M., 1993, COMPLEXITY NUMERICAL, P16

[6] Pseudo-Boolean optimization [J].

Boros, E ;

Hammer, PL .

DISCRETE APPLIED MATHEMATICS, 2002, 123 (1-3) :155-225

[7]

Charnes A., 1962, Naval Res Logist Quart, V9, P181, DOI [DOI 10.1002/NAV.3800090303, 10.1002/nav.3800090303]

[8]

Hansen P., 1990, ANN MATH ARTIF INTEL, V1, P97, DOI [10.1007/BF01531072, DOI 10.1007/BF01531072]

[9]

HANSEN P, 1991, MATH PROGRAM, V52, P256

[10] HOW EASY IS LOCAL SEARCH [J].

JOHNSON, DS ;

PAPADIMITRIOU, CH ;

YANNAKAKIS, M .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1988, 37 (01) :79-100

← 1 2 →