Minimization of half-products

被引：30

作者：

Badics, T

Boros, E

机构：

[1] Parametr Technol Corp, Waltham, MA 02154 USA

[2] Rutgers State Univ, RUTCOR, New Brunswick, NJ 08904 USA

来源：

MATHEMATICS OF OPERATIONS RESEARCH | 1998年 / 23卷 / 03期

关键词：

completion time variance minimization; quadratic binary minimization; fully polynomial approximation scheme;

D O I：

10.1287/moor.23.3.649

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper a special class of quadratic functions, the so called half-products are considered. It is shown that while the minimization over the set of binary n-vectors for half-products is NP-complete, an epsilon-approximating solution can be found in polynomial time for any epsilon > 0.

引用

页码：649 / 660

页数：12

共 9 条

[1]

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

[2]

Arora S., 1992, Proceedings 33rd Annual Symposium on Foundations of Computer Science (Cat. No.92CH3188-0), P14, DOI 10.1109/SFCS.1992.267823

[3]

Boros E., 1991, Annals of Operations Research, V33, P151, DOI 10.1007/BF02115753

[4] ON THE MINIMIZATION OF COMPLETION-TIME VARIANCE WITH A BICRITERIA EXTENSION [J].

DE, P ;

GHOSH, JB ;

WELLS, CE .

OPERATIONS RESEARCH, 1992, 40 (06) :1148-1155

[5]

DEZA M, 1992, BSR9221 CTR MATH COM

[6] MINIMIZING WAITING TIME VARIANCE IN SINGLE MACHINE PROBLEM [J].

EILON, S ;

CHOWDHURY, IG .

MANAGEMENT SCIENCE, 1977, 23 (06) :567-575

[7] COMPLETION-TIME VARIANCE MINIMIZATION ON A SINGLE-MACHINE IS DIFFICULT [J].

KUBIAK, W .

OPERATIONS RESEARCH LETTERS, 1993, 14 (01) :49-59

[8] THE BOOLEAN QUADRIC POLYTOPE - SOME CHARACTERISTICS, FACETS AND RELATIVES [J].

PADBERG, M .

MATHEMATICAL PROGRAMMING, 1989, 45 (01) :139-172

[9]

Palubeckis G., 1990, Informatica, V1, P89

← 1 →