New Results on the Probabilistic Analysis of Online Bin Packing and its Variants
New Results on the Probabilistic Analysis of Online Bin Packing and its Variants
![Open Access](/xmlui/themes/Fakultaeten//images/32px-Open_Access_logo_PLoS_white.svg.png)
dc.contributor.advisor | Röglin, Heiko | |
dc.contributor.author | Fischer, Carsten Oliver | |
dc.date.accessioned | 2020-04-27T01:23:15Z | |
dc.date.available | 2020-04-27T01:23:15Z | |
dc.date.issued | 03.12.2019 | |
dc.identifier.uri | https://hdl.handle.net/20.500.11811/8120 | |
dc.description.abstract | The classical bin packing problem can be stated as follows: We are given a multiset of items {a1, ..., an} with sizes in [0,1], and want to pack them into a minimum number of bins, each of which with capacity one. There are several applications of this problem, for example in the field of logistics: We can interpret the i-th item as time a package deliverer spends for the i-th tour. Package deliverers have a daily restricted working time, and we want to assign the tours such that the number of package deliverers needed is minimized. Another setup is to think of the items as boxes with a standardized basis, but variable height. Then, the goal is to pack these boxes into a container, which is standardized in all three dimensions. Moreover, applications of variants of the classical bin packing problem arise in cloud computing, when we have to store virtual machines on servers. Besides its practical relevance, the bin packing problem is one of the fundamental problems in theoretical computer science: It was proven many years ago that under standard complexity assumptions it is not possible to compute the value of an optimal packing of the items efficiently - classical bin packing is NP-complete. Computing the value efficiently means that the runtime of the algorithm is bounded polynomially in the number of items we have to pack. Besides the offline version, where we know all items at the beginning, also the online version is of interest: Here, the items are revealed one-by-one and have to be packed into a bin immediately and irrevocably without knowing which and how many items will still arrive in the future. Also this version is of practical relevance. In many situations we do not know the whole input at the beginning: For example we are unaware of the requirements of future virtual machines, which have to be stored, or suddenly some more packages have to be delivered, and some deliverers already started their tour. We can think of the classical theoretical analysis of an online algorithm A as follows: An adversary studies the behavior of the algorithm and afterwards constructs a sequence of items I. Then, the performance is measured by the number of used bins by A performing on I, divided by the value of an optimal packing of the items in I. The adversary tries to choose a worst-case sequence so this way to measure the performance is very pessimistic. Moreover, the chosen sequences I often turn out to be artificial: For example, in many cases the sizes of the items increase monotonically over time. Instances in practice are often subject to random influence and therefore it is likely that they are good-natured. In this thesis we analyze the performance of online algorithms with respect to two stochastic models.
| |
dc.language.iso | eng | |
dc.rights | In Copyright | |
dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | |
dc.subject | Algorithmen | |
dc.subject | Bin Packing | |
dc.subject | Bin Covering | |
dc.subject | Online | |
dc.subject | Probabilistische Analyse | |
dc.subject | Algorithms | |
dc.subject | Probabilistic Analysis | |
dc.subject.ddc | 004 Informatik | |
dc.title | New Results on the Probabilistic Analysis of Online Bin Packing and its Variants | |
dc.type | Dissertation oder Habilitation | |
dc.publisher.name | Universitäts- und Landesbibliothek Bonn | |
dc.publisher.location | Bonn | |
dc.rights.accessRights | openAccess | |
dc.identifier.urn | https://nbn-resolving.org/urn:nbn:de:hbz:5n-56711 | |
ulbbn.pubtype | Erstveröffentlichung | |
ulbbnediss.affiliation.name | Rheinische Friedrich-Wilhelms-Universität Bonn | |
ulbbnediss.affiliation.location | Bonn | |
ulbbnediss.thesis.level | Dissertation | |
ulbbnediss.dissID | 5671 | |
ulbbnediss.date.accepted | 12.09.2019 | |
ulbbnediss.institute | Mathematisch-Naturwissenschaftliche Fakultät : Fachgruppe Informatik / Institut für Informatik | |
ulbbnediss.fakultaet | Mathematisch-Naturwissenschaftliche Fakultät | |
dc.contributor.coReferee | Kesselheim, Thomas |
Files in this item
This item appears in the following Collection(s)
-
E-Dissertationen (4116)