Strusevich, Vitaly A. and Kellerer, Hans (2013) Approximation schemes for quadratic Boolean programming problems and their scheduling applications. In: OR55 Annual Conference - Keynote Papers and Extended Abstracts. Operational Research Society Limited, Birmingham, UK, pp. 73-85. ISBN 0903440555

PDF 12197_StrusevichKellerer_(FPV)_(2013).pdf - Published Version Restricted to Repository staff only Download (676kB) | Request a copy

Abstract

We consider Boolean programming problems with quadratic objective functions, related to the Half-Product introduced by Badics and Boros in 1998. The variants include problems of minimizing the Half-Product with an additive constant, convex positive Half-Product, a symmetric quadratic function, with and without a linear knapsack constraint. A methodology for designing fully polynomial-time approximation schemes (FPTASs) for these problems is presented. As one of the prerequisites for designing an FPTAS, the problem at hand must admit a constant-ratio approximation algorithm. We develop such algorithms by solving the continuous relaxation of a Boolean programming problem in strongly polynomial time followed by an appropriate rounding of the fractional variables. The problems under consideration serve as mathematical programming reformulations of a wide range of scheduling problems with mini-sum objective functions. The corresponding FPTASs can be adapted to be applicable to these scheduling problems.

Item Type:	Conference Proceedings
Title of Proceedings:	OR55 Annual Conference - Keynote Papers and Extended Abstracts
Additional Information:	[1] This Keynote paper was first presented at the OR 55 Annual Conference held from 3-5 September 2013 in Exeter, UK. And the full-text of the keynote conference paper is held on GALA with permission from the publisher.
Uncontrolled Keywords:	quadratic boolean programming, approximation, scheduling
Subjects:	Q Science > QA Mathematics
Faculty / School / Research Centre / Research Group:	Faculty of Engineering & Science > School of Computing & Mathematical Sciences (CMS) Faculty of Engineering & Science
Related URLs:	Organisation Organisation
Last Modified:	04 Mar 2022 13:08
URI:	http://gala.gre.ac.uk/id/eprint/12197

Actions (login required)

View Item

Downloads