Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.11851/8365
Title: Algorithmic Analysis of Priority-Based Bin Packing
Authors: Wojciechowski, P.
Subramani, K.
Velasquez, A.
Caskurlu, B.
Keywords: Parallel processing systems
Algorithmic analysis
Bin packing
Minimization problems
Positive integers
Priority assignment
Priority-based
Computational complexity
Issue Date: 2021
Publisher: Springer Science and Business Media Deutschland GmbH
Abstract: This paper is concerned with a new variant of Traditional Bin Packing (TBP) called Priority-Based Bin Packing with Subset Constraints (PBBP-SC). In a TBP instance, we are given a collection of items { a1, a2, … an}, with ai? (0, 1 ) and a collection of unit-size bins { B1, B2, …, Bm}. One problem associated with TBP is the bin minimization problem. The goal of this problem is to pack the items in as few bins as possible. In a PBBP-SC instance, we are given a collection of unit-size items and a collection of 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 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. Checking if there is a feasible assignment to a given instance is one problem. Finding a maximum priority assignment in case of the instance being infeasible is another. Finding an assignment with the fewest number of bins to pack a feasible instance is a third. We derive a number of results from both the algorithmic and computational complexity perspectives for these problems. © 2021, Springer Nature Switzerland AG.
Description: 7th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2021 -- 11 February 2021 through 13 February 2021 -- 253869
URI: https://doi.org/10.1007/978-3-030-67899-9_29
https://hdl.handle.net/20.500.11851/8365
ISBN: 9783030678982
ISSN: 0302-9743
Appears in Collections:Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection
Yapay Zeka Mühendisliği Bölümü / Department of Artificial Intelligence Engineering

Show full item record

CORE Recommender

Page view(s)

84
checked on Aug 8, 2022

Google ScholarTM

Check

Altmetric


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