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