Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.11851/10790
Full metadata record
DC FieldValueLanguage
dc.contributor.authorWojciechowski, P.-
dc.contributor.authorSubramani, K.-
dc.contributor.authorVelasquez, A.-
dc.contributor.authorCaskurlu, B.-
dc.date.accessioned2023-10-24T07:03:38Z-
dc.date.available2023-10-24T07:03:38Z-
dc.date.issued2024-
dc.identifier.issn0166-218X-
dc.identifier.urihttps://doi.org/10.1016/j.dam.2023.08.019-
dc.identifier.urihttps://hdl.handle.net/20.500.11851/10790-
dc.description.abstractThis 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.en_US
dc.description.sponsorshipDefense Advanced Research Projects Agency, DARPA: HR001123S0001-FP-004en_US
dc.description.sponsorshipThis research was supported in part by the Defense Advanced Research Projects Agency through grant HR001123S0001-FP-004 .en_US
dc.language.isoenen_US
dc.publisherElsevier B.V.en_US
dc.relation.ispartofDiscrete Applied Mathematicsen_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.subjectApproximationen_US
dc.subjectBin packingen_US
dc.subjectMatchingen_US
dc.subjectOptimizationen_US
dc.subjectSETHen_US
dc.subjectComputational complexityen_US
dc.subjectPolynomial approximationen_US
dc.subjectApproximationen_US
dc.subjectBin packingen_US
dc.subjectFeasibility problemen_US
dc.subjectMatchingsen_US
dc.subjectMaximization problemen_US
dc.subjectMinimization problemsen_US
dc.subjectOptimisationsen_US
dc.subjectPositive integersen_US
dc.subjectPriority-baseden_US
dc.subjectSETHen_US
dc.subjectParallel processing systemsen_US
dc.titlePriority-based bin packing with subset constraintsen_US
dc.typeArticleen_US
dc.departmentTOBB ETÜen_US
dc.identifier.volume342en_US
dc.identifier.startpage64en_US
dc.identifier.endpage75en_US
dc.identifier.wosWOS:001079843100001en_US
dc.identifier.scopus2-s2.0-85171174454en_US
dc.institutionauthor-
dc.identifier.doi10.1016/j.dam.2023.08.019-
dc.authorscopusid57205976247-
dc.authorscopusid8921210200-
dc.authorscopusid56404337600-
dc.authorscopusid35104543000-
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
item.fulltextNo Fulltext-
item.grantfulltextnone-
item.languageiso639-1en-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.openairetypeArticle-
item.cerifentitytypePublications-
Appears in Collections:Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection
WoS İndeksli Yayınlar Koleksiyonu / WoS Indexed Publications Collection
Show simple item record



CORE Recommender

Page view(s)

4
checked on May 6, 2024

Google ScholarTM

Check




Altmetric


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