💻 computer science

A 2.37332-Competitive Algorithm for Online Square Packing with Gravity

Dieses Papier stellt den $\mathrm{AsymmetricSlots}$ -Algorithmus vor, der eine 2,37332-kompetitive Ratio für das Online-Quadratpacken in einem Streifen mit der Einheitbreite unter Tetris- und Gravitationsbeschränkungen erreicht, wodurch die bisherige beste Schranke von etwa 2,6154 verbessert und gleichzeitig die optimale Abhängigkeit vom Aspektverhältnis für allgemeine Rechtecke etabliert wird.

Ursprüngliche Autoren: Nichlas Langhoff Rasmussen

Veröffentlicht 2026-09-10

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Nichlas Langhoff Rasmussen

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich eine Welt vor, in der Sie einen Turm bauen müssen, Block für Block, ohne jemals zu wissen, was als Nächstes kommt. Sie können die bereits platzierten Blöcke nicht umordnen und Sie können nicht in die Struktur hineingreifen, um sie zur Seite zu schieben. Jeder neue Block muss von oben herabfallen und senkrecht nach unten fallen, bis er auf dem obersten Teil des bestehenden Stapels oder auf dem Boden aufschlägt. Wenn eine Lücke im Turm existiert, aber durch einen breiteren Block von oben versperrt ist, ist diese Lücke nutzlos; nichts kann sie jemals erreichen. Dies ist die Herausforderung des Online-Packens unter Schwerkraft, ein Problem, das an der Schnittstelle von Geometrie und Logistik liegt. Es stellt eine einfache, aber hartnäckige Frage: Wie kann ein System die bestmöglichen Entscheidungen treffen, wenn es blind gegenüber der Zukunft und an die Gesetze der Physik gebunden ist?

Jahrelang konnte die beste bekannte Methode zum Stapeln quadratischer Blöcke auf diese Weise einen Turm garantieren, der nicht mehr als etwa das 2,62-fache der absoluten kürzesten Höhe eines Turms beträgt, den man erreicht hätte, wenn man alle Blöcke im Voraus gesehen hätte. Diese Lücke zwischen der Online-Realität und dem Offline-Ideal stellte eine erhebliche Ineffizienz dar. Forscher vermuteten schon lange, dass eine intelligentere Art der Raumorganisation diese Lücke schließen könnte, aber die Einschränkungen durch die Schwerkraft und der Mangel an Vorhersehung machten das Finden einer solchen Methode außergewöhnlich schwierig. Bei dem Problem geht es nicht nur darum, Formen ineinanderzufügen; es geht darum, den Fluss des Raumes zu verwalten, während dieser verbraucht wird, um sicherzustellen, dass der Pfad für zukünftige Blöcke offen bleibt, selbst während die aktuelle Struktur wächst.

Eine aktuelle Studie stellt eine neue Strategie namens AsymmetricSlots vor, die es erfolgreich schafft, diese Effizienzlücke zu verengen. Die Forscher entwickelten eine Methode, die die Worst-Case-Leistung des Packalgorithmus verbessert, indem sie beweist, dass der resultierende Turm niemals mehr als etwa das 2,37-fache der Höhe des perfekten, vorab geplanten Turms sein wird. Dies ist eine messbare Verbesserung gegenüber dem bisherigen besten Ergebnis und bringt die theoretische Grenze des Online-Quadratpackens signifikant näher an das Ideal. Die Arbeit behauptet nicht, das Problem vollständig gelöst zu haben, da eine Lücke zwischen diesem neuen oberen Grenzwert und dem bekannten unteren Grenzwert von 2 besteht, aber sie etabliert einen neuen, höheren Standard für das Machbare.

Der Kern dieses neuen Ansatzes liegt darin, wie der verfügbare Raum aufgeteilt wird. Frühere Methoden behandelten den vertikalen Raumstreifen als eine Serie von gleich großen, geschachtelten Kompartimenten, wobei die Breite auf jeder Ebene zur Hälfte geteilt wurde. Der neue Algorithmus bricht diese Symmetrie. Anstatt den Raum gleichmäßig aufzuteilen, teilt er jedes verfügbare Slot in zwei ungleiche Kinder auf: eines breites und eines schmales. Wenn ein neues Quadrat eintrifft, entscheidet der Algorithmus, wohin es gesendet werden soll, basierend auf seiner Größe im Verhältnis zu diesen ungleichen Teilungen. Wenn ein Quadrat zu groß für das schmale Kind ist, wird es gezwungen, in das breite Kind zu gehen. Wenn es klein genug ist, um in beide zu passen, schickt der Algorithmus es dorthin, wo der Stapel an Blöcken derzeit niedriger ist. Dieser lokale Entscheidungsprozess, der sich wiederholt, während das Quadrat durch die Hierarchie der Slots nach unten sinkt, ermöglicht es dem System, die Last effektiver auszubalancieren als die alten symmetrischen Methoden.

Um zu beweisen, dass diese Strategie funktioniert, verwendeten die Forscher eine Methode der Buchführung, die die „Kosten“ jedes platzierten Quadrats verfolgt. Sie stellten sich vor, dass jedes Quadrat die Höhe, die es dem Turm hinzufügt, mit seiner eigenen Fläche als Währung bezahlt. Große Quadrate, die in bestimmte Slots gezwungen sind, bezahlen ihre eigene Höhe direkt. Kleinere Quadrate, die die Flexibilität haben, zwischen Slots zu wählen, werden durch ein System temporärer Gutschriften gehandhabt, die sich im Laufe der Zeit ausgleichen. Die Analyse zeigt, dass der Effizienzverlust, der durch diese flexiblen Entscheidungen verursacht wird, nicht mit dem Wachstum des Turms kumuliert; stattdin bleibt er begrenzt. Dieser mathematische Beweis bestätigt, dass die Leistung des Algorithmus stabil und vorhersehbar ist, unabhängig von der Sequenz der empfangenen Blöcke.

Die Studie erweitert diese Logik auch auf Rechtecke, die keine perfekten Quadrate sind, aber in ihrer Länge und Breite begrenzt sind. Für diese Formen fanden die Forscher heraus, dass die Effizienz des Packens direkt von dem maximalen Verhältnis der Länge eines Rechtecks zu seiner Breite abhängt. Sie bewiesen, dass mit steigendem Verhältnis die Schwierigkeit des Packens in einer vorhersehbaren, linearen Weise zunimmt. Dieses Ergebnis deutet darauf hin, dass die Methode robust ist und auf eine größere Vielfalt von Formen angewendet werden kann, sofern die Formen nicht unendlich dünn werden. Umgekehrt zeigten sie auch, dass kein Online-Algorithmus signifikant besser als diese lineare Beziehung agieren kann, was bedeutet, dass die Abhängigkeit von den Proportionen der Form grundlegend für das Problem selbst ist.

Obwohl der neue Algorithmus einen bedeutenden Schritt nach vorn darstellt, weisen die Forscher vorsichtig darauf hin, dass das Problem noch nicht vollständig gelöst ist. Sie konstruierten spezifische Szenarien, in denen ihr neuer Algorithmus einen Turm erzeugt, der doppelt so hoch ist wie die optimale Offline-Lösung, was zeigt, dass die Lücke zwischen der besten möglichen Online-Leistung und dem theoretischen Ideal immer noch beträchtlich ist. Der Unterschied zwischen dem neuen oberen Grenzwert von etwa 2,37 und dem unteren Grenzwert von 2 bleibt eine weite Kluft, die Mathematiker überbrücken müssen. Durch die Etablierung eines neuen, engeren Grenzwerts und die Bereitstellung eines Rahmens, der sowohl Quadrate als auch begrenzte Rechtecke handhabt, klärt diese Arbeit jedoch die Landschaft des Problems. Sie zeigt, dass mit der richtigen Art der asymmetrischen Organisation die Einschränkungen durch die Schwerkraft und die Unkenntnis der Zukunft mit größerer Präzision verwaltet werden können, als bisher angenommen wurde.

Technisches Resümee: Ein 2,37332-kompetitiver Algorithmus für das Online-Quadratpacken mit Gravitation

Problemdefinition
Die Arbeit befasst sich mit dem Online-Streifenpackproblem für achsenparallele Quadrate unter Tetris- und Gravitationsbeschränkungen. In diesem Modell treffen Quadrate sequenziell ein, ohne Kenntnis über zukünftige Elemente zu haben, und müssen unumkehrbar in einem Streifen der Breite 1 und unbeschränkter Höhe platziert werden.

Tetris-Beschränkung: Ein eintreffendes Quadrat muss einem kollisionsfreien, monoton abwärts gerichteten Pfad von oben nach seiner Endposition folgen.
Gravitations-Beschränkung: Das Quadrat muss auf dem Streifenboden oder auf der Oberseite bereits platzierter Quadrate zur Ruhe kommen.
Machbarkeit: Eine geometrisch leere Region kann unbrauchbar sein, wenn sie über einen Abwärtspfad nicht erreichbar ist oder keine Stütze besitzt.

Das Ziel ist es, die Gesamthöhe der Packung zu minimieren. Die Leistung wird durch das asymptotische kompetitive Verhältnis ( $CR$ ) gemessen, definiert als das Infimum von $\rho$ , so dass $A(\sigma) \le \rho \cdot OPT(\sigma) + \beta$ für alle Eingabesequenzen $\sigma$ gilt, wobei $A(\sigma)$ die Höhe des Algorithmus und $OPT(\sigma)$ die optimale Offline-Höhe ist.

Methodik: AsymmetricSlots
Der Autor führt AsymmetricSlots ein, einen rekursiven Algorithmus, der den bisher besten bekannten Ansatz, den SlotAlgorithm (Fekete et al., 2014), der eine dyadische (symmetrische) Hierarchie verwendete, verbessert.

Asymmetrische Hierarchie:
Anstatt einen Slot der Breite $w$ in zwei gleich große Hälften zu teilen, teilt der Algorithmus ihn in ein breites Kind der Breite $pw$ und ein schmales Kind der Breite $qw$ auf, wobei $p \in (1/2, 1)$ und $q = 1-p$ gilt. Diese Hierarchie steht fest, bevor irgendwelche Elemente eintreffen.
Lokale Routing-Regeln:
Bei der Ankunft eines Quadrats der Seitenlänge $a$ bewegt sich dieses basierend auf seiner Größe im Verhältnis zur aktuellen Slot-Breite $w$ durch die Hierarchie abwärts:

Direkt (Direct): Wenn $a > pw$, wird das Quadrat sofort dem aktuellen Slot zugewt.
Erzwungen (Forced): Wenn $qw < a \le pw$ , wird das Quadrat in das breite Kind gezwungen.
Flexibel (Flexible): Wenn $a \le qw$ , wird das Quadrat an das Kind mit der geringeren aktuellen virtuellen Höhe geleitet (bei Gleichstand wird das breite Kind bevorzugt).

Virtuelles Höhenprofil & Machbarkeit:
Der Algorithmus führt ein stückweise konstantes virtuelles Höhenprofil $h(x)$ zur Steuerung des Routings. Einem Slot $T$ , dem ein Quadrat zugewiesen wird, wird die Seitenlänge $a$ zur virtuellen Höhe seines Intervalls hinzugefügt.

Lemma 1 beweist, dass trotz der Tatsache, dass das virtuelle Profil die physische Höhe potenziell überschätzt, die physische Insertion unter Tetris- und Gravitationsbeschränkungen immer machbar ist. Speziell kann das physische Quadrat immer auf ein Unterstützungslage $y^*$ (bestimmt durch vorhandene Quadrate oder den Streifenboden) fallen, die $\le$ dem virtuellen Aktualisierungsniveau entspricht, wodurch Kollisionen während des Abstiegs ausgeschlossen werden.

Analyse mittels lokaler Verrechnung (Local Charging):
Der Beweis nutzt ein lokales Phasen-Invariante und ein Verrechnungsargument, das die Asymmetrie der Aufteilung ausnutzt:

Erzwungene Quadrate: Große Quadrate ($a > qw$) werden in spezifische Pfade gezwungen. Ihre Fläche ist ausreichend, um die von ihnen erzeugte Höhe zu „bezahlen“ ( $wa - \rho a^2 \le 0$ ).
Flexible Quadrate: Kleine Quadrate ( $a \le qw$ ) ermöglichen ein Ausbalancieren zwischen den Kindern. Die Analyse nutzt eine „phasenbasierte“ Buchführung, bei der der Algorithmus ein Guthaben $\delta w^2$ hält. Die Asymmetrie stellt sicher, dass der Verlust im Zusammenhang mit flexiblen Platzierungen lokal begrenzt ist und nicht mit der Tiefe der Hierarchie akkumuliert.
Phasenabschluss (Phase Closure): Eine Phase eines Slots endet, wenn ein „direktes“ Quadrat (eines, das zu groß für die Kinder ist) platziert wird, was das virtuelle Profil zurücksetzt.

Wichtigste Ergebnisse

Verbesserte obere Schranke für Quadrate:
Durch Optimierung des Aufteilungsparameters $p$ leitet der Autor ein kompetitives Verhältnis von 2,373318506... ab.

Der optimale Parameter $p^\star$ ist die eindeutige Wurzel in $(1/2, 1)$ von $16p^3 - 8p^2 + p - 1 = 0$ , was $p^\star \approx 0,5786$ ergibt.
Das resultierende Verhältnis ist $\rho^\star = 1/(1-p^\star) \approx 2,3733$ .
Eine rationale Näherung unter Verwendung von $p = 11/19$ liefert ein klares Verhältnis von 2,375 ( $19/8$ ).
Dies verbessert die bisherige beste obere Schranke von $34/13 \approx 2,6154$ , die von Fekete et al. etabliert wurde.

Untere Schranke für den Algorithmus:
Das Paper etabliert eine spezifische untere Schranke für AsymmetricSlots. Mittels einer Konstruktion mit wiederholten Quadraten zeigen die Autoren, dass für ein $p$ in einem Bereich, der $p^\star$ enthält, das kompetitive Verhältnis mindestens 2 beträgt.

Somit gilt $2 \le CR(AsymmetricSlots_{p^\star}) \le 2,3733...$
Die allgemeine untere Schranke für jeden deterministischen Online-Algorithmus in diesem Modell bleibt $3/2$ (von Fekete et al.).

Erweiterung auf Rechtecke:
Das Framework wird auf Rechtecke mit einem beschränkten Seitenverhältnis $\kappa$ erweitert (wobei Breite $u$ und Höhe $v$ die Bedingung $u/\kappa \le v \le \kappa u$ erfüllen).

Obere Schranke: Der Algorithmus erreicht ein asymptotisches kompetitives Verhältnis von $O(\kappa)$ .
Untere Schranke: Eine passende $\Omega(\kappa)$ untere Schranke wird durch eine alternierende Konstruktion von schmalen vertikalen und breiten, flachen Rechtecken bewiesen.
Dies etabliert, dass die optimale Abhängigkeit vom Seitenverhältnis $\Theta(\kappa)$ ist.

Bedeutung und Ansprüche
Das Paper behauptet, die beste bekannte obere Schranke für das Online-Quadratpackproblem unter Tetris- und Gravitationsbeschränkungen zu liefern, indem das kompetitive Verhältnis von $\approx 2,6154$ auf $\approx 2,3733$ reduziert wird.

Methodischer Beitrag: Der Übergang von einer symmetrischen (dyadischen) zu einer asymmetrischen rekursiven Zerlegung ermöglicht ein effizienteres lokales Verrechnungsargument. Die Asymmetrie trennt Platzierungen in „erzwungene“ (große) und „flexible“ (kleine) Kategorien, wodurch die Akkumulation von Fehlertermen verhindert wird, die frühere Analysen erschwert hatten.
Geltungsbereich: Die Ergebnisse sind rein theoretisch und konzentrieren sich auf die kompetitive Analyse deterministischer Algorithmen. Das Paper beansprucht nicht, das allgemeine Offline-Problem zu lösen oder ein Polynomial-Time Approximation Scheme für den Offline-Fall bereitzustellen.
Einschränkungen: Der Autor merkt an, dass die Lücke zwischen der algorithmus-spezifischen unteren Schranke (2) und der oberen Schranke (2,3733) weiterhin besteht, ebenso wie die Lücke zwischen der allgemeinen unteren Schranke (1,5) und der oberen Schranke. Das Paper legt nahe, dass zukünftige Arbeiten nicht-selbstähnliche Aufteilungen oder mehr als zwei Teil-Slots untersuchen könnten, um diese Lücken potenziell zu schließen.

Zusammenfassend verfeinert die Arbeit die theoretischen Grenzen des Online-Quadratpackens unter physikalischen Beschränkungen und zeigt, dass eine asymmetrische hierarchische Zerlegung ein streng besseres kompetitives Verhältnis liefert als zuvor bekannte symmetrische Ansätze.

Technisches Resümee: Ein 2,37332-kompetitiver Algorithmus für das Online-Quadratpacken mit Gravitation

Mehr davon