Skip navigation

Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints

Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints

Halman, Nir, Kellerer, Hans and Strusevich, Vitaly A. (2018) Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints. European Journal of Operational Research, 270 (2). pp. 435-447. ISSN 0377-2217 (doi:https://doi.org/10.1016/j.ejor.2018.04.013)

[img]
Preview
PDF (Publisher's PDF - Open Access)
20042 STRUSEVICH_Approximation_Schemes_for_Non-Separable_Non-Linear_Boolean_(OA)_2018.pdf - Published Version
Available under License Creative Commons Attribution.

Download (686kB) | Preview
[img]
Preview
PDF (Author Accepted Manuscript)
20042 STRUSEVICH_Approximation_Schemes_for_Non-Separable_Non-Linear_Boolean_Programming_2018.pdf - Accepted Version
Available under License Creative Commons Attribution.

Download (376kB) | Preview

Abstract

We consider a fairly general model of “take-or-leave”decision-making. Given a number of items of a particular weight, the decision-maker either takes (accepts) an item or leaves (rejects) it. We design fully polynomial-time approximation schemes (FPTASs) for optimization of a non-separable non-linear function which depends on which items are taken and which are left. The weights of the taken items are subject to nested constraints. There is a noticeable lack of approximation results on integer programming problems with non-separable functions. Most of the known positive results address special forms of quadratic functions, and in order to obtain the corresponding approximation algorithms and schemes considerable technical difficulties have to be overcome. We demonstrate how for the problem under consideration and its modifications FPTASs can be designed by using (i) the geometric rounding techniques, and (ii) methods of K -approximation sets and functions. While the latter approach leads to a faster scheme, the running times of the of both algorithms compare favorably with known analogues for less general problems.

Item Type: Article
Additional Information: © 2018 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license. (http://creativecommons.org/licenses/by/4.0/)
Uncontrolled Keywords: Combinatorial optimization; Non-linear boolean programming; Geometric rounding; K -approximation sets and functions, FPTAS
Subjects: Q Science > QA Mathematics
Faculty / Department / Research Group: Faculty of Architecture, Computing & Humanities
Faculty of Architecture, Computing & Humanities > Department of Mathematical Sciences
Last Modified: 16 May 2019 10:15
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: GREAT b
Selected for GREAT 2019: GREAT 3
URI: http://gala.gre.ac.uk/id/eprint/20042

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics