Citation
T. Badics et E. Boros, Minimization of half-products, MATH OPER R, 23(3), 1998, pp. 649-660
Citations number
9
Categorie Soggetti
Mathematics
Journal title
MATHEMATICS OF OPERATIONS RESEARCH
ISSN journal
0364765X
→ ACNP
Volume
23
Issue
3
Year of publication
1998
Pages
649 - 660
Database
ISI
SICI code
0364-765X(199808)23:3<649:MOH>2.0.ZU;2-C
Abstract
In this paper a special class of quadratic functions, the so called half-pr
oducts are considered. It is shown that while the minimization over the set
of binary n-vectors for half-products is NP-complete, an epsilon-approxima
ting solution can be found in polynomial time for any epsilon > 0.