COMPLEXITY OF UNIQUENESS AND LOCAL SEARCH IN QUADRATIC 0-1 PROGRAMMING

被引：56

作者：

PARDALOS, PM ^{[1
]}

JHA, S ^{[1
]}

机构：

[1] CARNEGIE MELLON UNIV,DEPT COMP SCI,PITTSBURGH,PA 15213

来源：

OPERATIONS RESEARCH LETTERS | 1992年 / 11卷 / 02期

关键词：

QUADRATIC; 0-1; PROGRAMMING; NP-HARD; UNIQUENESS; LOCAL SEARCH; COMPUTATIONAL RESULTS;

D O I：

10.1016/0167-6377(92)90043-3

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We prove that the problem of checking whether a quadratic 0-1 problem has a unique solution is NP-hard. Furthermore, we prove that finding the global minimum of quadratic 0-1 programming with unique solution remains an NP-hard problem. Regarding local search, we prove that the problem of finding a discrete local minimum for quadratic 0-1 problems, with two coordinates being fixed, is NP-hard. In addition, we discuss an algorithm for computing discrete local minima.

引用

页码：119 / 123

页数：5

共 13 条

[1] RECOGNITION PROBLEMS FOR SPECIAL CLASSES OF POLYNOMIALS IN 0-1 VARIABLES [J].

CRAMA, Y .

MATHEMATICAL PROGRAMMING, 1989, 44 (02) :139-155

[2]

Hansen P., 1979, Discrete Optimisation, P53

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

JOHNSON, DS ;

PAPADIMITRIOU, CH ;

YANNAKAKIS, M .

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

[4]

Papadimitriou C. H., 1982, 23rd Annual Symposium on Foundations of Computer Science, P14, DOI 10.1109/SFCS.1982.28

[5]

Pardalos P. M., 1990, Annals of Operations Research, V22, P271, DOI 10.1007/BF02023057

[6] GRAPH SEPARATION TECHNIQUES FOR QUADRATIC ZERO-ONE PROGRAMMING [J].

PARDALOS, PM ;

JHA, S .

COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1991, 21 (6-7) :107-113

[7] COMPUTATIONAL ASPECTS OF A BRANCH AND BOUND ALGORITHM FOR QUADRATIC ZERO-ONE PROGRAMMING [J].

PARDALOS, PM ;

RODGERS, GP .

COMPUTING, 1990, 45 (02) :131-144

[8] CONSTRUCTION OF TEST PROBLEMS IN QUADRATIC BIVALENT PROGRAMMING [J].

PARDALOS, PM .

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 1991, 17 (01) :74-87

[9] CHECKING LOCAL OPTIMALITY IN CONSTRAINED QUADRATIC-PROGRAMMING IS NP-HARD [J].

PARDALOS, PM ;

SCHNITGER, G .

OPERATIONS RESEARCH LETTERS, 1988, 7 (01) :33-35

[10]

PARDALOS PM, 1989, IMPACTS RECENT COMPU, P131

← 1 2 →