{"entities":{"Q3838010":{"pageid":5867915,"ns":120,"title":"Item:Q3838010","lastrevid":108368336,"modified":"2026-11-06T03:24:21Z","type":"item","id":"Q3838010","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1183280"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3838010$E90A1B60-20EB-4839-9CA3-5AE4FB825DB6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0ae0586fc9c179641f4399bb03807090bc995ed2","datavalue":{"value":"0903.90137","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3838010$216367C5-6F4C-4F7B-BC24-25E00BC48421","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"835631c6a47bbed7bc42fe28ab357f81c2ca5ee6","datavalue":{"value":{"entity-type":"item","numeric-id":207995,"id":"Q207995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3838010$33CC85C7-4BE8-4000-A757-D89FEA2EADEF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fda7d68dde2ce269daa4d7eb5af1d4726eca7412","datavalue":{"value":{"time":"+1998-08-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3838010$1E380423-567E-49FB-91F9-F14578B52DEC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3838010$615F3B5E-D21B-4DB5-BEE5-73A6E1408FC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3838010$33910529-1BE3-4FD2-9E2E-3F6F78956476","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3838010$7DDF4D75-A202-453B-8899-A4F5B0ADBE65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3838010$A428AFD3-B97F-4AB8-B46A-7A250A508287","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0d13153341c32bd0ad833225a36194bdbaef7bdc","datavalue":{"value":"1183280","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3838010$C88D121D-5611-448E-8118-473C3ACFA8D1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"773e01723cba2d6ae5824c15f2ac9987378c44c4","datavalue":{"value":"packing patterns","type":"string"},"datatype":"string"},"type":"statement","id":"Q3838010$222639E7-1BBA-4769-B8E2-53A6528DF2D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d59ab2c83e0dbd443ebc1f3d0412b712509c0917","datavalue":{"value":"interval graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q3838010$410A817C-12AC-4A0A-8928-7B383D34BD5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea53e49e7d1bad5ad321e9db46065c8f107e8edd","datavalue":{"value":"asymptotic worst case performance","type":"string"},"datatype":"string"},"type":"statement","id":"Q3838010$F4269637-A32F-4D17-857B-39040311248D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93486d73f813d47f3c650ed53f02e62423fbfa93","datavalue":{"value":"orthogonal knapsack problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q3838010$02066FF1-8E91-407E-9788-B09CEB198991","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3838010$03ABD795-4F5E-4D3C-87D7-07FABB722DED","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd1d16c9e551136bd830248125ce3e30d90ff812","datavalue":{"value":{"entity-type":"item","numeric-id":2643952,"id":"Q2643952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2db2b139fda8941178c8018167cad283e84fabb","datavalue":{"value":{"amount":"+0.8420996069908142","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3838010$39D6D878-7E77-40E9-B176-ECA32A262A59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c8342bb119c283bb25b12efaf39324cefe6e9e8","datavalue":{"value":{"entity-type":"item","numeric-id":3392097,"id":"Q3392097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21c6e5a915e5e5ce2d28d7a289073d28fee2b53b","datavalue":{"value":{"amount":"+0.8365681171417236","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3838010$AC51B0D6-B650-48B0-838D-1408F40281B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"911b094962f4df2dea43288f9f1d8ebaed7f88ad","datavalue":{"value":{"entity-type":"item","numeric-id":4233347,"id":"Q4233347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2532379537612c4f3802e2c9fc3c43ec8a407c2","datavalue":{"value":{"amount":"+0.8329735994338989","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3838010$527AB7C2-E0EA-401E-A586-F9F50F1C88F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64ada585c818118c0f6bc63c0c1462fd3a05f889","datavalue":{"value":{"entity-type":"item","numeric-id":826081,"id":"Q826081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea231cb6d87cb899ad36c9331045ca37f2249412","datavalue":{"value":{"amount":"+0.8315790891647339","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3838010$C8B5B487-FB86-4D52-97AA-1AD4F2FA5B1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa3e29101648c92cf76c1b3a985843398b7a06af","datavalue":{"value":{"entity-type":"item","numeric-id":2029021,"id":"Q2029021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38b6b69499db0c71c0ace6673a006788854db242","datavalue":{"value":{"amount":"+0.8155515193939209","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3838010$CEED9E13-084D-4C4A-9A70-9C4BA36D4ED7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"14ed60785cab031f87a2929965d8ae023416c8f2","datavalue":{"value":"Im zweiten Kapitel haben wir \\(d\\)-dimensionale Packmuster mit Hilfe von Intervallgraphen charakterisiert und so den Begriff der Packmusterklasse eingef\u00fchrt. Die daraus im vierten Kapitel abgeleitete enumerative Methode f\u00fcr das orthogonale Entscheidungsproblem besitzt zwei Vorteile: Erstens erreichen wir eine gewisse Symmetriereduktion, da wir statt Packmustern ganze Packmusterklassen enumerieren. Zweitens beschleunigen die starken Struktureigenschaften der Intervallgraphen den Suchproze\u00df, indem sie effektive Kriterien zum Abschneiden von \u00c4sten des Suchbaums liefern. Wir konnten zudem das \u00dcberpr\u00fcfen dieser Kriterien durch effiziente Algorithmen auf perfekten Graphen realisieren. Im dritten Kapitel haben wir mit den Volumenbilanzen bez\u00fcglich konservativer Skalierungen eine allgemeine Methode gefunden, Relaxierungen und Schranken f\u00fcr orthogonale Packungsprobleme zu konstruieren. Eine einfache Herleitung mehrdimensionaler Schranken erm\u00f6glicht insbesondere unsere Erkenntnis, da\u00df man eine konservative Skalierung erh\u00e4lt, wenn man auf jede Komponente der Gr\u00f6\u00dfenfunktion eine beliebige dual zul\u00e4ssige Funktion anwendet. Wir haben drei Klassen dual zul\u00e4ssiger Funktionen angegeben, aus denen sich so in linearer Zeit berechenbare konservative Skalierungen konstruieren lassen. In diesem Rahmen haben wir f\u00fcr bekannte Schranken vereinfachte und systematisierte Darstellungen gefunden, die zudem preiswerte Verbesserungsm\u00f6glichkeiten offenbarten. Weiterhin haben wir gezeigt, wie man dual zul\u00e4ssige Funktionen zur heuristischen Verbesserung beliebiger unterer Schranken f\u00fcr das eindimsionale BPP benutzen kann. Mit dieser Technik konnten wir sowohl die asymptotische Worst-Case-Performance als auch die ``empirische'' Performance der bisher besten ``billigen'' unteren Schranke f\u00fcr das BPP erheblich steigern. Im f\u00fcnften Kapitel haben wir die in den vorigen Kapiteln entwickelten Methoden als Bausteine f\u00fcr neue exakte Algorithmen f\u00fcr \\(d\\)-dimensionale orthogonale Packungsprobleme verwendet. Das Verfahren f\u00fcr das orthogonale Knapsackproblem wurde implementiert und auf zwei- und dreidimensionalen Instanzen getestet. Unsere numerischen Resultate belegen, da\u00df das neue Verfahren einen deutlichen Fortschritt darstellt: F\u00fcr jede \u00f6ffentlich zug\u00e4ngliche OKP-2-Testinstanz konnte in weniger als 0.4 Sekunden eine Optimall\u00f6sung berechnet werden. Die maximale Anzahl der Boxen einer exakt gel\u00f6sten OKP-2-Instanz wurde von 22 auf 80 gesteigert, die maximale Anzahl der Boxtypen von 15 auf 40. Diese Gr\u00f6\u00dfen geben keine singul\u00e4ren Extremf\u00e4lle wieder, sondern beziehen sich jeweils auf ganze Klassen nichttrivialer Testinstanzen. Anders als bei den bisher existierenden Verfahren stellt die Containergr\u00f6\u00dfe keinen limitierenden Faktor dar. In dieser Arbeit werden nach unserem Wissen zum ersten Mal experimentelle Resultate f\u00fcr ein OKP-3-Verfahren ver\u00f6ffentlicht. Bei einem geringen Anteil kleiner Boxen konnten hier ebenso gro\u00dfe Instanzen bearbeitet werden wie beim OKP-2. Doch selbst bei einem 60\\%-Anteil kleiner Boxen konnten immerhin noch OKP-3-Instanzen mit 20 Boxen zuverl\u00e4\u00dfig exakt gel\u00f6st werden. Die in dieser Arbeit erzielten Ergebnisse ermutigen dazu, exakte Verfahren auf geeignete Praxisprobleme anzuwenden. Die hier beschriebenen Algorithmen bieten daf\u00fcr einen guten Ausgangspunkt. Aussichtsreich erscheint etwa ein hybrider Ansatz, bei dem zun\u00e4chst die sperrigen Objekte mit exakten Verfahren gepackt, und sp\u00e4ter die kleinen Objekte mit einer Heuristik in die L\u00fccken geschoben werden. Dazu w\u00fcrde sich die Push-Straight-Insert-Heuristik eignen. Auch k\u00f6nnten gewisse praktische Nebenbedingungen, wie z.B. die vorgeschriebene r\u00e4umliche Trennung verschiedener Gefahrgutbeh\u00e4lter innerhalb eines Frachtcontainers direkt in den Ansatz integriert werden, indem mit ihnen ein Teil der Packmusterklasse a priori bestimmt wird. Die Erzeugung von Schranken mit Hilfe konservativer Skalierungen ist als eine allgemeine Technik sicherlich auch au\u00dferhalb des Kontexts dieser Arbeit verwertbar. Eine naheliegende und praktisch relevante Anwendung w\u00e4re zum Beispiel die Integration dieser Schranken in Guillotinenschnittverfahren.","type":"string"},"datatype":"string"},"type":"statement","id":"Q3838010$C0D6159B-318E-4C59-8CAE-BF408369E893","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3838010","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3838010"}}}}}