Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorWojciechowski, P.-
dc.contributor.authorSubramani, K.-
dc.contributor.authorVelasquez, A.-
dc.contributor.authorCaskurlu, B.-
dc.description7th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2021 -- 11 February 2021 through 13 February 2021 -- 253869en_US
dc.description.abstractThis 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.en_US
dc.description.sponsorshipFA9550-19-1-0177; Air Force Research Laboratory, AFRL: FA8750-17-S-7007en_US
dc.description.sponsorshipThis research is supported in part by the Air-Force of Scientific Research through Grant FA9550-19-1-0177 and in part by the Air-Force Research Laboratory, Rome through Contract FA8750-17-S-7007.en_US
dc.publisherSpringer Science and Business Media Deutschland GmbHen_US
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_US
dc.subjectParallel processing systemsen_US
dc.subjectAlgorithmic analysisen_US
dc.subjectBin packingen_US
dc.subjectMinimization problemsen_US
dc.subjectPositive integersen_US
dc.subjectPriority assignmenten_US
dc.subjectComputational complexityen_US
dc.titleAlgorithmic Analysis of Priority-Based Bin Packingen_US
dc.typeConference Paperen_US
dc.departmentFaculties, Faculty of Engineering, Department of Artificial Intelligence Engineeringen_US
dc.departmentFakülteler, Mühendislik Fakültesi, Yapay Zeka Mühendisliği Bölümütr_TR
dc.identifier.volume12601 LNCSen_US
dc.institutionauthorÇaşkurlu, Buğra-
dc.relation.publicationcategoryKonferans Öğesi - Uluslararası - Kurum Öğretim Elemanıen_US
item.openairetypeConference Paper-
item.fulltextNo Fulltext-
item.cerifentitytypePublications- Department of Computer Engineering-
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 simple item record

CORE Recommender

Page view(s)

checked on Oct 3, 2022

Google ScholarTM



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