On the approximability of the two-phase knapsack problem

Kameng Nip () and Zhenbo Wang
Additional contact information
Kameng Nip: Sun Yat-sen University
Zhenbo Wang: Tsinghua University

Journal of Combinatorial Optimization, 2019, vol. 38, issue 4, No 11, 1155-1179

Abstract: Abstract We consider a natural generalization of the knapsack problem and the multiple knapsack problem, which has two phases of packing decisions. In this problem, we have a set of items, several small knapsacks called boxes, and a large knapsack called container. Each item has a size and profit, each box has a size and the container has a capacity. The first phase is to select some items to pack into the boxes, and the second phase is to select the boxes (each includes some packed items) to pack into the container. The total profit of the problem is determined by the items that are selected and packed into the container within some packed box, and the objective is to maximize the total profit. This problem is motivated by various practical applications, e.g., in logistics. It is a generalization of the multiple knapsack problem, and hence is strongly NP-hard. We mainly propose three approximation algorithms for it. Particularly, the first one is a $$\frac{1}{4}$$ 1 4 -approximation algorithm based on its linear programming relaxation; the second one is based on applying the algorithms for the multiple knapsack problem and the knapsack problem, and has an approximation ratio $$\frac{1}{3} - \epsilon $$ 1 3 - ϵ for any small enough $$\epsilon >0$$ ϵ > 0 . We finally provide a polynomial time approximation scheme for this problem.

Keywords: Two-phase knapsack; Multiple knapsack; Approximation algorithms; Polynomial time approximation scheme (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00442-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:38:y:2019:i:4:d:10.1007_s10878-019-00442-w

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00442-w

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().