Online bin stretching with three bins

Kód výsledku v IS VaVaI

RIV/00216208:11320/17:10368750 - isvavai.cz

Výsledek na webu

http://dx.doi.org/10.1007/s10951-016-0504-y

DOI - Digital Object Identifier

10.1007/s10951-016-0504-y

Jazyk výsledku

angličtina

Název v původním jazyce

Online bin stretching with three bins

Popis výsledku v původním jazyce

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 for three bins. Additionally, we present a lower bound of for online bin stretching on three bins and a lower bound of 19/14 for four and five bins that were discovered using a computer search.

Název v anglickém jazyce

Online bin stretching with three bins

Popis výsledku anglicky

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 for three bins. Additionally, we present a lower bound of for online bin stretching on three bins and a lower bound of 19/14 for four and five bins that were discovered using a computer search.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

GA14-10003S: Omezené typy výpočtů: algoritmy, modely, složitost

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Scheduling

ISSN

1094-6136

e-ISSN

—

Svazek periodika

20

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

21

Strana od-do

601-621

Kód UT WoS článku

000416152200006

EID výsledku v databázi Scopus

—