Campus Event Calendar
Event Entry
What and Who
Round&Round: An Improved Algorithm for 2-Dimensional Vector Bin Packing
Ariel Kulik
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 16 November 2021
13:00
30 Minutes
Virtual talk
Virtual talk
Saarbrücken
Abstract
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.
Contact
Virtual Meeting Details
Zoom
527 278 8807
public
Tags, Category, Keywords and additional notes
If you are interested in attending the talk, please contact Roohani Sharma rsharma@mpi-inf.mpg.de for the password of the zoom meeting.
Roohani Sharma, 11/08/2021 14:54
Roohani Sharma, 11/08/2021 14:51 -- Created document.
Roohani Sharma, 11/08/2021 14:51 -- Created document.