Bin Packing

Inhalt des Vortrags:

• Vorstellung des Problems

• Die Strategie Next Fit (lege nächstes Objekt in aktiven Eimer, falls es passt, andernfalls schließe aktiven Eimer und öffne einen neuen)
  • ist 2-kompetitiv (denn wenn in Eimer i noch p viel Platz ist, ist in Eimer i+1 mindestens p Platz belegt)

  • kann diese Schranke tatsächlich erreichen (betrachte für Eimer der Höhe 1 eine Folge von Objekten der Höhen , , , ,... mit sehr kleinem )

• Die Strategie First Fit (lege nächstes Objekt in den ersten Eimer von links, in den es hineinpasst)
  • ist 2-kompetitiv (denn bis auf höchstens einen sind alle benutzten Eimer mindestens halb voll)

  • ist sogar 1,7-kompetitiv (ohne Beweis)

• Vergleich Next Fit - First Fit: Laufzeit O - O, bei Next Fit nur jeweils ein Eimer zugänglich (beengter Laderaum)

• Jede kompetitive Strategie fuer Bin Packing ist mindestens - kompetitiv (sei S eine c-kompetitive Strategie. Ärgere sie mit einer Folge aus m Objekten der Höhe , gefolgt von m Objekten der Höhe . Angenommen, die ersten m Objekte werden von S in b Eimern untergebracht; dann ist , denn viele Eimer wären optimal. Insgesamt muss S mindestens 2m-b viele Eimer belegen, denn es sind 2m Objekte zu verpacken, und höchstens die ersten b Eimer können doppelt belegt sein. Also gilt , und insgesamt folgt .)

• optional: Bin Packing ist NP-vollstaendig

Literatur:

Garey, Johnson: Computers and Intractability, p. 124-126

Fiat, Woeginger (eds.): Online Algorithms, p. 150

Betreuer:
Rolf Klein