NP-hardness of linear multiplicative programming and related problems

被引：161

作者：

Matsui, T ^{[1
]}

机构：

[1] UNIV TOKYO,FAC ENGN,DEPT MATH ENGN & INFORMAT PHYS,BUNKYO KU,TOKYO 113,JAPAN

来源：

JOURNAL OF GLOBAL OPTIMIZATION | 1996年 / 9卷 / 02期

关键词：

NP-hard; minimization of products; linear multiplicative programming; linear fractional programming; multi-ratio programming;

D O I：

10.1007/BF00121658

中图分类号：

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

学科分类号：

070105 [运筹学与控制论]; 12 [管理学]; 1201 [管理科学与工程]; 1202 [工商管理学]; 120202 [企业管理];

摘要：

The linear multiplicative programming problem minimizes a product of two (positive) variables subject to linear inequality constraints. In this paper, we show NP-hardness of linear multiplicative programming problems and related problems.

引用

页码：113 / 119

页数：7

共 15 条

[1]

ON A CLASS OF QUADRATIC PROGRAMS [J].

ANEJA, YP ;

AGGARWAL, V ;

NAIR, KPK .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1984, 18 (01) :62-70

[2]

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

[3]

[Anonymous], 1972, COMPLEXITY COMPUTER

[4]

LINEAR MULTIPLICATIVE PROGRAMMING [J].

KONNO, H ;

KUNO, T .

MATHEMATICAL PROGRAMMING, 1992, 56 (01) :51-64

[5]

Konno H., 1990, Annals of Operations Research, V25, P147, DOI 10.1007/BF02283691

[6]

KONNO H, IN PRESS GLOBAL OPTI

[7]

KONNO H, 1992, COMPUTATIONAL OPTIMI, V1, P227

[8]

KONNO H, 1995, HDB GLOBAL OPTIMIZAT

[9]

KONNO H, 1991, J GLOBAL OPTIM, V1, P65

[10]

Kuno T., 1991, J GLOB OPTIM, V1, P267

← 1 2 →