⚡ Box Packing is Hard - Keegan R

Channel:
United Kingdom UWCS - University of Warwick Computing Society
Subscribers:
2,970
Published on ● Video Link: https://www.youtube.com/watch?v=E9WCI_kkO6k


Duration: 17:48
3,177 views
143

A seemingly simple talk about trying to put boxes in boxes. What could go wrong?

No prizes for guessing, but quite a lot actually. We'll explore what assumptions we can make to simplify this box packing problem, explore algorithms that might (or might not) help, and see if we can find any reasonable guarantee depending on the dimension.

Challenge:
Can you find an equation, or algorithm, for determining the maximum number of boxes that can be packed using the strategy mentioned at 12:34 ? The more efficient your time complexity, the better!

Further Reading:
https://en.wikipedia.org/wiki/Square_packing_in_a_square
https://www.combinatorics.org/ojs/index.php/eljc/article/view/v17i1r126/pdf

Talk by Keegan R

00:00 - Introduction
01:07 - Motivation
03:37 - How do we even solve this?
07:04 - What about 2D?
09:26 - Oh Dear
13:19 - The Third Dimension
16:15 - Final Attempt



Other Videos By UWCS - University of Warwick Computing Society


2023-03-24The Graduate Experience - Abhyuday R
2023-03-08Why AI Academia is Dying (and how to fix it) - Herbie B
2023-03-05Why Rust is bad, actually*
2023-03-03⚡ How Computers (try to) Keep Time - Joel C
2023-01-28Java: What They Don't Teach You
2022-12-24⚡Interpreting Neural Networks - Avi S
2022-12-21⚡ Type Level Arithmetic in Haskell - Felix B
2022-12-19⚡ Formal Concept Analysis - Josh F
2022-11-18🐍 Python Intermediate: File Handling & The Command Line
2022-11-02🦀 UWCS Learns Rust: Don't Panic!
2022-10-27⚡ Box Packing is Hard - Keegan R
2022-10-26🐍 Python Basics: Lists & Loops
2022-10-25⚡ Making Servers Gossip - Tomás F
2022-10-24🐍 Python Basics: Flow Control & Functions
2022-10-23⚡ Pokemon's Save Corruption Speedrun - Sammy Y
2022-10-22🦀 UWCS Learns Rust: Fighting the Borrow Checker
2022-10-19🐍 Python Basics: Variables, Datatypes, Debugging
2022-10-14🦀 UWCS Learns Rust: Hello, Ferris!
2022-10-03Git Good: Version Control Basics - Sam Coy
2022-07-18⚡ The Basics of 3D Printing - Edward U
2022-07-17⚡ Synthetic Data Generation for Machine Learning - Josh H


Tags:
computing
uwcs
university
society
coding
programming
discrete maths
mathematics
discrete
bin packing
shape fitting
containers
NP
NP-Complete
NP-Hard
algorithms
maths
problem-solving
lightning talk
computing society
talk
optimisation
box packing
square packing
packing problems
computer science
trigonometry
logistic problem
box packing problem
square packing problem
shape packing
geometry
computationally hard