{"id":189410,"date":"2013-05-29T00:00:00","date_gmt":"2013-05-31T12:06:11","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/tight-bound-for-online-vector-packing\/"},"modified":"2016-08-02T06:12:00","modified_gmt":"2016-08-02T13:12:00","slug":"tight-bound-for-online-vector-packing","status":"publish","type":"msr-video","link":"https:\/\/www.microsoft.com\/en-us\/research\/video\/tight-bound-for-online-vector-packing\/","title":{"rendered":"Tight Bound for Online Vector Packing"},"content":{"rendered":"<div class=\"asset-content\">\n<p>In the d-dimensional vector bin packing problem (VBP), one is given d-dimensional real vectors x<sub>1<\/sub>,x<sub>2<\/sub>, \u2026 ,x<sub>n<\/sub>  and the goal is to find a partition into a minimum number of feasible sets. A set is feasible if the sum of its elements is less than the all 1\u2019s vector. For online VBP, it has been outstanding for almost 20 years to clarify the gap between the best lower bound Omega(1) on the competitive ratio versus the best  upper bound of O(d).<\/p>\n<p>We settle this by describing a Omega(d<sup>1-&epsilon;<\/sup>) lower bound. We also give strong lower bounds (of &Omega;(d<sup>frac 1B-&epsilon;<\/sup>) ) if the bin size  B in Z_+ is allowed to grow. Finally, we discuss almost-matching upper bound results for general values of B; we show an upper bound whose exponent  is additively \u201cshifted by 1&#8243; from the lower bound exponent.<\/p>\n<p>Joint work with: Yossi Azar, Seny Kamara and Bruce Shepherd<\/p>\n<\/div>\n<p><!-- .asset-content --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>In the d-dimensional vector bin packing problem (VBP), one is given d-dimensional real vectors x1,x2, \u2026 ,xn and the goal is to find a partition into a minimum number of feasible sets. A set is feasible if the sum of its elements is less than the all 1\u2019s vector. For online VBP, it has been [&hellip;]<\/p>\n","protected":false},"featured_media":197642,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr_hide_image_in_river":0,"footnotes":""},"research-area":[],"msr-video-type":[206954],"msr-locale":[268875],"msr-post-option":[],"msr-session-type":[],"msr-impact-theme":[],"msr-pillar":[],"msr-episode":[],"msr-research-theme":[],"class_list":["post-189410","msr-video","type-msr-video","status-publish","has-post-thumbnail","hentry","msr-video-type-microsoft-research-talks","msr-locale-en_us"],"msr_download_urls":"","msr_external_url":"https:\/\/youtu.be\/Q21egz8Kjs\/","msr_secondary_video_url":"","msr_video_file":"","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/189410","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-video"}],"version-history":[{"count":0,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/189410\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/197642"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=189410"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=189410"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=189410"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=189410"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=189410"},{"taxonomy":"msr-session-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-session-type?post=189410"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=189410"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=189410"},{"taxonomy":"msr-episode","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-episode?post=189410"},{"taxonomy":"msr-research-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-theme?post=189410"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}