דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
אריאל קוליק (CISPA Helmholtz Center for Information Security
event date icon
יום רביעי, 29.12.2021, 12:30
event location icon
טאוב 201
We study the 2-Dimensional Vector Bin Packing Problem (2VBP), a generalization of classic Bin Packing that is widely applicable in resource allocation and scheduling. In 2BVP we are given a set of items, where each item is associated with a two-dimensional volume vector. The objective is to partition the items into a minimal number of subsets (bins), such that the total volume of items in each subset is at most 1 in each dimension. We give an asymptotic 25/18+ eps ~ 1.389-approximation for the problem, thus improving upon the best known asymptotic ratio of (1+ln 3/2+ eps) ~1.406 due to Bansal, Elias and Khan. Our algorithm applies a novel Round&Round approach which iteratively solves a configuration-LP relaxation for the residual instance and samples a small number of configurations based on the solution for the configuration-LP. For the analysis we derive an iteration-dependent upper bound on the solution size for the configuration-LP, which holds with high probability. We obtain the improved ratio by exploiting key structural properties of 2VBP instances in a fractional manner, using new ideas and techniques which are of independent interest.