This HTML5 document contains 45 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
n24http://linked.opendata.cz/ontology/domain/vavai/riv/typAkce/
dctermshttp://purl.org/dc/terms/
n22http://purl.org/net/nknouf/ns/bibtex#
n11http://localhost/temp/predkladatel/
n17http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n7http://linked.opendata.cz/resource/domain/vavai/projekt/
n18http://linked.opendata.cz/resource/domain/vavai/subjekt/
n3http://linked.opendata.cz/ontology/domain/vavai/
n8https://schema.org/
shttp://schema.org/
n6http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F00216208%3A11320%2F13%3A10190764%21RIV14-GA0-11320___/
rdfshttp://www.w3.org/2000/01/rdf-schema#
skoshttp://www.w3.org/2004/02/skos/core#
n5http://linked.opendata.cz/ontology/domain/vavai/riv/
n21http://bibframe.org/vocab/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n23http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n20http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n16http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n12http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n14http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n9http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n15http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F00216208%3A11320%2F13%3A10190764%21RIV14-GA0-11320___
rdf:type
n3:Vysledek skos:Concept
rdfs:seeAlso
http://dx.doi.org/10.4230/LIPIcs.STACS.2013.538
dcterms:description
In the bin packing problem we are given an instance consisting of a sequence of items with sizes between 0 and 1. The objective is to pack these items into the smallest possible number of bins of unit size. FirstFit algorithm packs each item into the first bin where it fits, possibly opening a new bin if the item cannot fit into any currently open bin. In early seventies it was shown that the asymptotic approximation ratio of FirstFit bin packing is equal to 1.7. We prove that also the absolute approximation ratio for FirstFit bin packing is exactly 1.7. In the bin packing problem we are given an instance consisting of a sequence of items with sizes between 0 and 1. The objective is to pack these items into the smallest possible number of bins of unit size. FirstFit algorithm packs each item into the first bin where it fits, possibly opening a new bin if the item cannot fit into any currently open bin. In early seventies it was shown that the asymptotic approximation ratio of FirstFit bin packing is equal to 1.7. We prove that also the absolute approximation ratio for FirstFit bin packing is exactly 1.7.
dcterms:title
First Fit bin packing: A tight analysis First Fit bin packing: A tight analysis
skos:prefLabel
First Fit bin packing: A tight analysis First Fit bin packing: A tight analysis
skos:notation
RIV/00216208:11320/13:10190764!RIV14-GA0-11320___
n3:predkladatel
n18:orjk%3A11320
n5:aktivita
n16:P
n5:aktivity
P(GBP202/12/G061), P(IAA100190902)
n5:dodaniDat
n15:2014
n5:domaciTvurceVysledku
n17:8679673
n5:druhVysledku
n9:D
n5:duvernostUdaju
n20:S
n5:entitaPredkladatele
n6:predkladatel
n5:idSjednocenehoVysledku
75178
n5:idVysledku
RIV/00216208:11320/13:10190764
n5:jazykVysledku
n12:eng
n5:klicovaSlova
online algorithms; bin packing; First Fit
n5:klicoveSlovo
n23:online%20algorithms n23:bin%20packing n23:First%20Fit
n5:kontrolniKodProRIV
[6AA0A61FCB82]
n5:mistoKonaniAkce
Kiel
n5:mistoVydani
Dagstuhl, Germany
n5:nazevZdroje
30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
n5:obor
n14:IN
n5:pocetDomacichTvurcuVysledku
1
n5:pocetTvurcuVysledku
2
n5:projekt
n7:IAA100190902 n7:GBP202%2F12%2FG061
n5:rokUplatneniVysledku
n15:2013
n5:tvurceVysledku
Sgall, Jiří Dósa, Gyorgy
n5:typAkce
n24:WRD
n5:zahajeniAkce
2013-02-27+01:00
s:issn
1868-8969
s:numberOfPages
12
n21:doi
10.4230/LIPIcs.STACS.2013.538
n22:hasPublisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
n8:isbn
978-3-939897-50-7
n11:organizacniJednotka
11320