Ausarbeitung des Papers „Improved algorithms for multidimensional bin packing problems“ von Nikhil Bansal, Alberto Caprara und Maxim Sviridenko

FELIX THOMSEN

Kiel

Seminario; Seminar Theoretische Informatik:; 2007

Christian-Albrechts-Universität zu Kiel, Institut für Informatik

Dieser Arbeit liegt der Artikel „Improved approximation algorithms for multidimensionalbin packing problems“ zugrunde, in dem verschiedene Teilprobleme abgeschätzt werden.Das d-dim-Vector-Packing wird durch einen randomisierten Algorithmus in polynomiellerZeit mit einer Approximierungsgarantie nahe bei ln d+1 abgeschätzt. Damit wird fürden Wert d = 2 die natürliche Schranke von 2 überwunden. Für kleine Werte von d bietetdies darüberhinaus eine bemerkenswerte Verbesserung gegenüber der bereits bekanntenO(ln d) Garantie von Chekuri und Khanna.Im Falle des 2-dimensionalen Bin-Packing mit und ohne Rotation werden Algorithmenmit Performance-Garantie von ungefähr 1:525 : : : gezeigt, die zum einen die Performance-Garantie von 2 + " für die Variante mit Rotation verbessert, und zum anderen dieSchranke von 1.691... für die Variante ohne Rotation bricht.Ein weiteres Beiprodukt des Papers ist ein Algorithmus, der eine bekannte LP-Konfigurationfür das 2-dimensionale Bin-Packing für alle " > 0 mit einem Faktor von (1+") löst. Obwohldas Separations- und Optimierungsproblem äquivalent sind und die Existenz einesApproximierungschemas für das Separationsproblem weiterhin offen bleibt, wird gezeigt,dass es möglich ist, ein Approximierungsschema für die betreffende LP-Konfiguration zunennen, wenn die betrachtete Funktion ungewichtet ist.