On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem
- PDF / 755,584 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 30 Downloads / 238 Views
On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem Britta Schulze1 · Michael Stiglmayr1 · Luís Paquete2 · Carlos M. Fonseca2 · David Willems3 · Stefan Ruzika4 Received: 16 January 2019 / Revised: 7 January 2020 © The Author(s) 2020
Abstract In this article, we introduce the rectangular knapsack problem as a special case of the quadratic knapsack problem consisting in the maximization of the product of two separate knapsack profits subject to a cardinality constraint. We propose a polynomial time algorithm for this problem that provides a constant approximation ratio of 4.5. Our experimental results on a large number of artificially generated problem instances show that the average ratio is far from theoretical guarantee. In addition, we suggest refined versions of this approximation algorithm with the same time complexity and approximation ratio that lead to even better experimental results. Keywords Quadratic knapsack problem · Approximation algorithm · Multiobjective combinatorial optimization · Hypervolume
1 Introduction The classical (linear) knapsack problem (KP) is a combinatorial optimization problem. Given a finite set {1, . . . , n} of items i with assigned profit and weight values pi and wi , respectively, and a finite capacity W , KP decides which items to include to maximize the total profit while satisfying a capacity constraint. The capacity and profit and weight values are all assumed to be positive integer and each item can be included at most once. KP is an N P-complete problem but is solvable in pseudo-polynomial time by dynamic programming. Several interesting and challenging variants of KP
B
Britta Schulze [email protected]
1
Department of Mathematics and Natural Sciences, University of Wuppertal, Gaußstr. 20, 42119 Wuppertal, Germany
2
Department of Informatics Engineering, CISUC, University of Coimbra, Coimbra, Portugal
3
Mathematical Institute, University of Koblenz-Landau, Koblenz, Germany
4
Department of Mathematics, University of Kaiserslautern, Kaiserslautern, Germany
123
B. Schulze et al.
have been introduced in the past (see (Kellerer et al. 2004) for an overview). One of those is the quadratic knapsack problem (QKP). In contrast to KP, the profit of a collection of items in QKP is not only determined by the sum of individual profits, but also by profits generated by pairwise combinations of items. This can be used to model the fact that two items may complement each other such that their profit is increased if both of them are selected. The quadratic objective still allows to model that the profit of two items is independent of each other by setting the combined profit to 0. In this case, including both items does not increase the profit over the sum of the individual profits. Furthermore, a negative combined profit value can model the fact that both items together are less profitable than the sum of individual profits. This might be the case, if both items are substitutes for each other and including both items is as
Data Loading...
