1 00:00:02,130 --> 00:00:04,850 It's Flashcard Fridays at Math Science History. 2 00:00:05,050 --> 00:00:07,710 I'm Gabrielle Birchak, and today we're going to 3 00:00:07,710 --> 00:00:11,390 take a quick trip into the suitcase. 4 00:00:12,070 --> 00:00:12,610 Literally. 5 00:00:13,470 --> 00:00:15,690 But first, a word from our advertisers. 6 00:00:16,590 --> 00:00:18,450 Have you ever found yourself sitting on your 7 00:00:18,450 --> 00:00:21,410 luggage, desperately trying to zip it shut? 8 00:00:21,630 --> 00:00:24,950 Or playing Tetris with your shoes, socks, t 9 00:00:24,950 --> 00:00:25,930 -shirts, and pants? 10 00:00:28,450 --> 00:00:31,850 Believe it or not, this problem has fascinated 11 00:00:31,850 --> 00:00:34,010 mathematicians and computer scientists. 12 00:00:34,230 --> 00:00:36,830 It really has, especially when you're a fashionista. 13 00:00:37,050 --> 00:00:39,050 Well, a nerdy fashionista like me. 14 00:00:39,330 --> 00:00:42,250 It's called a packing problem, and it's all 15 00:00:42,250 --> 00:00:43,590 about optimization. 16 00:00:44,250 --> 00:00:46,090 Let's take a closer look at how this 17 00:00:46,090 --> 00:00:49,050 mathematical idea helps you get the most out 18 00:00:49,050 --> 00:00:51,710 of your luggage, and how it applies far 19 00:00:51,710 --> 00:00:52,890 beyond travel. 20 00:00:53,590 --> 00:00:54,990 Like, if you have a purse. 21 00:00:56,410 --> 00:00:59,170 Which I do, and I often lose things. 22 00:00:59,570 --> 00:01:01,990 So, this podcast is going to serve me 23 00:01:01,990 --> 00:01:02,310 well. 24 00:01:02,690 --> 00:01:04,530 So, what are packing problems? 25 00:01:05,070 --> 00:01:08,090 Packing problems fall into a category of mathematics 26 00:01:08,090 --> 00:01:10,630 called combinatorial optimization. 27 00:01:11,270 --> 00:01:12,750 The basic idea is this. 28 00:01:13,090 --> 00:01:14,950 How do you fit a set of items 29 00:01:14,950 --> 00:01:17,170 with different shapes and sizes into a limited 30 00:01:17,170 --> 00:01:19,390 space as efficiently as possible? 31 00:01:19,830 --> 00:01:23,190 There are two-dimensional packing problems, like arranging 32 00:01:23,190 --> 00:01:26,430 photos in a collage, 3D packing problems like 33 00:01:26,430 --> 00:01:28,970 your suitcase or a shipping container, and even 34 00:01:28,970 --> 00:01:32,530 multi-dimensional ones that exist in data science. 35 00:01:32,870 --> 00:01:35,290 One of the most famous in data science 36 00:01:35,290 --> 00:01:36,990 is the bin packing problem. 37 00:01:37,370 --> 00:01:40,250 Imagine you're trying to pack items into as 38 00:01:40,250 --> 00:01:43,030 few bins as possible without exceeding the bin's 39 00:01:43,030 --> 00:01:44,430 weight or volume limit. 40 00:01:44,690 --> 00:01:48,590 This exact scenario is used in logistics, airline 41 00:01:48,590 --> 00:01:51,970 cargo loading, and even cloud storage algorithms. 42 00:01:52,490 --> 00:01:53,970 But why is it so hard? 43 00:01:54,470 --> 00:01:55,670 Okay, here's the twist. 44 00:01:56,250 --> 00:01:59,990 Packing problems are what we call NP-hard 45 00:01:59,990 --> 00:02:01,230 in computer science. 46 00:02:01,570 --> 00:02:04,870 That means there's no known fast algorithm that 47 00:02:04,870 --> 00:02:07,850 always gives the best solution, especially when the 48 00:02:07,850 --> 00:02:09,590 number of items grow. 49 00:02:09,930 --> 00:02:11,850 In real life, when you're packing your suitcase, 50 00:02:12,030 --> 00:02:14,570 you're solving a simplified version of a three 51 00:02:14,570 --> 00:02:16,390 -dimensional bin packing problem. 52 00:02:16,790 --> 00:02:20,330 But unlike a machine, you're using instinct, muscle 53 00:02:20,330 --> 00:02:22,290 memory, and visual estimation. 54 00:02:22,750 --> 00:02:26,210 That's why a perfectly packed suitcase feels so 55 00:02:26,210 --> 00:02:27,370 satisfying. 56 00:02:27,710 --> 00:02:31,150 It's a little victory in an unsolvable world. 57 00:02:31,450 --> 00:02:32,890 That is until you get to the airport 58 00:02:32,890 --> 00:02:34,950 and you have to pay for your luggage. 59 00:02:35,270 --> 00:02:37,330 That's another story for another time. 60 00:02:37,690 --> 00:02:39,450 So here are some tips from the math 61 00:02:39,450 --> 00:02:39,810 world. 62 00:02:40,330 --> 00:02:43,470 How do the pros, or the algorithms, do 63 00:02:43,470 --> 00:02:43,730 it? 64 00:02:43,990 --> 00:02:46,370 Well, first, they sort by size. 65 00:02:46,630 --> 00:02:49,890 Always pack the largest and bulkiest items first. 66 00:02:50,150 --> 00:02:52,590 This is a classic strategy in optimization. 67 00:02:53,070 --> 00:02:55,130 Get the hardest pieces out of the way. 68 00:02:55,530 --> 00:02:56,670 Two, fill the gaps. 69 00:02:56,930 --> 00:02:59,690 After the big items are in, use smaller 70 00:02:59,690 --> 00:03:02,630 things to fill the awkward spaces, like socks 71 00:03:02,630 --> 00:03:03,570 inside shoes. 72 00:03:04,090 --> 00:03:06,510 This is called greedy filling. 73 00:03:07,290 --> 00:03:08,950 Three, rotate for fit. 74 00:03:09,270 --> 00:03:13,470 Just like rotating puzzle pieces or rotating those 75 00:03:13,470 --> 00:03:16,990 Tetris pieces on the game Tetris, rotating items 76 00:03:16,990 --> 00:03:18,590 can make a huge difference. 77 00:03:18,950 --> 00:03:22,410 In mathematical terms, this is considering an item's 78 00:03:22,410 --> 00:03:24,190 degrees of freedom. 79 00:03:24,990 --> 00:03:27,190 Four, roll, don't fold. 80 00:03:27,750 --> 00:03:31,770 Rolling clothes makes them more compact and stackable. 81 00:03:32,050 --> 00:03:34,970 Kind of like using soft, pliable pieces in 82 00:03:34,970 --> 00:03:37,230 a game of spatial optimization. 83 00:03:37,890 --> 00:03:41,150 So some packing apps and shipping software actually 84 00:03:41,150 --> 00:03:45,090 use algorithms inspired by this math, like heuristic 85 00:03:45,090 --> 00:03:48,450 solvers or genetic algorithms to get close to 86 00:03:48,450 --> 00:03:51,650 the best possible solution in a short amount 87 00:03:51,650 --> 00:03:52,330 of time. 88 00:03:52,750 --> 00:03:55,930 So here are your takeaways for this week, 89 00:03:56,150 --> 00:03:58,190 especially if you're going on vacation. 90 00:03:58,190 --> 00:04:01,790 Packing your suitcase is a real world math 91 00:04:01,790 --> 00:04:02,310 problem. 92 00:04:02,550 --> 00:04:05,190 It's an NP hard one. 93 00:04:05,490 --> 00:04:05,910 That's right. 94 00:04:06,410 --> 00:04:09,830 Optimization techniques like sorting, rotating, and greedy filling 95 00:04:09,830 --> 00:04:13,530 are key strategies, and packing problems show up 96 00:04:13,530 --> 00:04:17,430 in shipping, logistics, cloud storage, and even warehouse 97 00:04:17,430 --> 00:04:18,170 robots. 98 00:04:18,670 --> 00:04:20,269 So the next time you zip up your 99 00:04:20,269 --> 00:04:22,150 luggage, give yourself a high five. 100 00:04:22,330 --> 00:04:25,630 You just solved a math problem that stumps 101 00:04:25,630 --> 00:04:26,470 computers. 102 00:04:27,030 --> 00:04:28,350 You are a mathematician. 103 00:04:29,150 --> 00:04:31,370 Thank you for joining me today on Flashcard 104 00:04:31,370 --> 00:04:33,850 Fridays, and if you liked this bite-sized 105 00:04:33,850 --> 00:04:36,770 brain boost, don't forget to subscribe and leave 106 00:04:36,770 --> 00:04:37,230 a review. 107 00:04:37,530 --> 00:04:39,330 You can find show notes and more fun 108 00:04:39,330 --> 00:04:41,770 facts at mathsciencehistory.com. 109 00:04:41,970 --> 00:04:44,850 And until next time, pack smart, stay curious, 110 00:04:45,150 --> 00:04:46,430 and carpe diem.