ML p(r)ior | A Two-Phase Algorithm for Bin Stretching with Stretching Factor 1.5

A Two-Phase Algorithm for Bin Stretching with Stretching Factor 1.5

2016-01-29
Online Bin Stretching is a semi-online variant of bin packing in which the algorithm has to use the same number of bins as an optimal packing, but is allowed to slightly overpack the bins. The goal is to minimize the amount of overpacking, i.e., the maximum size packed into any bin. We give an algorithm for Online Bin Stretching with a stretching factor of 1.5 for any number of bins. We build on previous algorithms and use a two-phase approach. However, our analysis is technically more complicated and uses amortization over the bins with the help of two weight functions.
PDF

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

Related Articles

2018-10-05
1810.02567 | stat.ML

We introduce a new model for online ranking in which the click probability factors into an examinati… show more
PDF

Highlights - Most important sentences from the article

2019-05-20

Online algorithms that allow a small amount of migration or recourse have been intensively studied i… show more
PDF

Highlights - Most important sentences from the article

2019-04-30

The bin covering problem asks for covering a maximum number of bins with an online sequence of $n$ i… show more
PDF

Highlights - Most important sentences from the article

2019-05-14

The advice model of online computation captures the setting in which the online algorithm is given s… show more
PDF

Highlights - Most important sentences from the article

2019-04-13

Semi-online models where decisions may be revoked in a limited way have been studied extensively in … show more
PDF

Highlights - Most important sentences from the article

2019-05-13
1905.04897 | cs.DS

Problems involving the efficient arrangement of simple objects, as captured by bin packing and makes… show more
PDF

Highlights - Most important sentences from the article

2019-05-09
1905.03838 | cs.DS

Quantiles, such as the median or percentiles, provide concise and useful information about the distr… show more
PDF

Highlights - Most important sentences from the article

2019-02-13

Although the performance of base-line Evolutionary Algorithms (EAs) on linear functions has been stu… show more
PDF

Highlights - Most important sentences from the article

2018-08-22

Cookie Clicker is a popular online incremental game where the goal of the game is to generate as man… show more
PDF

Highlights - Most important sentences from the article

2018-12-28
1812.11149 | cs.GT

We consider the online problem in which an intermediary trades identical items with a sequence of n … show more
PDF

Highlights - Most important sentences from the article

2019-02-09
1902.03422 | cs.DS

We present new approximation schemes for bin packing based on the following two approaches: (1) part… show more
PDF

Highlights - Most important sentences from the article

2018-10-29
1810.12086 | cs.DS

We consider several extensions of the fractional bin packing problem, a relaxation of the traditiona… show more
PDF

Highlights - Most important sentences from the article

2018-11-23
1811.09573 | cs.DS

We slightly improve the known lower bound on the asymptotic competitive ratio for online bin packing… show more
PDF

Highlights - Most important sentences from the article

2018-07-15

We improve the lower bound on the asymptotic competitive ratio of any online algorithm for bin packi… show more
PDF

Highlights - Most important sentences from the article

2017-05-19

In Packet Scheduling with Adversarial Jamming packets of arbitrary sizes arrive over time to be tran… show more
PDF

Highlights - Most important sentences from the article

2016-06-21

Online matching has received significant attention over the last 15 years due to its close connectio… show more
PDF

Highlights - Most important sentences from the article