Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.11851/10790
Title: Priority-based bin packing with subset constraints
Authors: Wojciechowski, P.
Subramani, K.
Velasquez, A.
Caskurlu, B.
Keywords: Approximation
Bin packing
Matching
Optimization
SETH
Computational complexity
Polynomial approximation
Approximation
Bin packing
Feasibility problem
Matchings
Maximization problem
Minimization problems
Optimisations
Positive integers
Priority-based
SETH
Parallel processing systems
Issue Date: 2024
Publisher: Elsevier B.V.
Abstract: This paper is concerned with a new variant of bin packing called priority-based bin packing with subset constraints (PBBP-SC). PBBP-SC is a variant of traditional bin packing (TBP). In a TBP instance, we are given a collection of items {t1,t2,…tn}, where each item ti has size si∈(0,1). The goal of TBP is to pack the items in as few unit-sized bins as possible. In a PBBP-SC instance, we are given a collection of n unit-size items and a collection of m bins of varying capacities. Associated with each item is a positive integer which is called its priority. The priority of an item indicates its importance in being included in a (possibly infeasible) packing. As with the traditional case, these items need to be packed in the fewest number of bins. What complicates the problem is the fact that each item can be assigned to only one of a select set of bins, i.e., the bins are not interchangeable. We investigate several problems associated with PBBP-SC. The first problem we study is the feasibility problem. This is the problem of checking if there is a feasible assignment to a given PBBP-SC instance. The second problem we study is the priority maximization problem. This is the problem of finding a maximum priority assignment of an infeasible PBBP-SC instance. The third problem we study is the bin minimization problem. This is the problem of finding an assignment with the fewest number of bins to pack all of the items in a feasible PBBP-SC instance. We derive a number of results from both the algorithmic and computational complexity perspectives for these problems. In particular, we show that both the feasibility and priority maximization problems are solvable in polynomial time. We also show that the bin minimization problem is log-APX-complete and cannot be solved in time o(1.41m) unless the Strong Exponential Time Hypothesis fails. © 2023 Elsevier B.V.
URI: https://doi.org/10.1016/j.dam.2023.08.019
https://hdl.handle.net/20.500.11851/10790
ISSN: 0166-218X
Appears in Collections:Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection
WoS İndeksli Yayınlar Koleksiyonu / WoS Indexed Publications Collection

Show full item record



CORE Recommender

Google ScholarTM

Check




Altmetric


Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.