In dieser Vorlesung machen wir einen Exkurs und beschäftigen und mit Optimierungsmethoden für mehrdimensionales Packen.
Folien: VL10.pdf
Video: [YouTube], [IBR]
Zusätzliche Links
1D Bin Packing. [PDF]
S.P. Fekete, J. Schepers.
New Classes of Fast Lower Bounds for Bin Packing Problems.
Mathematical Programming, 91 (2001), pp. 11-31.
Höher-Dimensionales Packen. [PDF]
S.P. Fekete, J. Schepers.
A Combinatorial Characterization of Higher-Dimensional Orthogonal Packing.
Mathematics of Operations Research, 29 (2004), pp. 353-368.
An Exact Algorithm for Higher-Dimensional Orthogonal Packing. [PDF]
S.P. Fekete, J. Schepers, J. van der Veen.
Operations Research, Vol. 55, No. 3, 2007, pp. 569-587.
Origami und Kreispacken. [PDF]
E.D. Demaine, S.P. Fekete, R.J. Lang.
Circle packing for Origami is Hard.
In: P. Wang-Iverson, R.J. Lang, M. Yim (eds.), Origami5: Fifth International Meeting of Origami Science, Mathematics, and Education, AK Peters/CRC Press, 2011, pp.609-626.
Dichtes Packen. [PDF]
S.P. Fekete, S. Morr, C. Scheffer.
Split Packing: Algorithms for Packing Circles with Optimal Worst-Case Density.
Discrete and Computational Geometry, 61(3), 2019, pp. 562-594.
Packing Geometric Objects with Optimal Worst-Case Density. [PDF] [Video – IBR]
A. Becker, S.P. Fekete, P. Keldenich, S. Morr, C. Scheffer.
In: 35th International Symposium on Computational Geometry (SoCG 2019), pp. 63:1-63:6.
Packing Squares into a Disk with Optimal Worst-Case Density. [PDF]
S.P. Fekete, V. Gurunathan, K. Juneja, P. Keldenich, C. Scheffer.
In: Symposium on Computational Geometry (SoCG 2021), LIPIcs vol. 189, pp. 36:1-36:16.
Dichtes Überdecken. [PDF] [Video – YouTube]
S.P. Fekete, P. Keldenich, C. Scheffer.
Covering Rectangles by Disks: The Video.
In: Symposium on Computational Geometry (SoCG 2020), LIPIcs vol. 164, pp. 75:1-75:5.
Worst-Case Optimal Covering of Rectangles by Disks. [PDF]
S.P. Fekete, U. Gupta, P. Keldenich, C. Scheffer, S. Shah.
In: Symposium on Computational Geometry (SoCG 2020), LIPIcs vol. 164, pp. 42:1-42:23.
Online-Packen. [PDF]
S.P. Fekete, C. Scheffer, S. von Höveling.
Online Circle Packing.
In: Proceedings of the 16th Algorithms and Data Structures Symposium (WADS 2019), pp. 366-379.
Online Square-in-Square Packing. [PDF]
S.P. Fekete, H.-F. Hoffmann.
In: Algorithmica, 77(3) 2017, 867-901.
Online square packing with gravity. [PDF]
S.P. Fekete, T. Kamphans, N. Schweer.
In: Algorithmica, 68(4), 2014, pp. 1019-1044.