Translate to multiple languages

Subscribe to my Email updates

https://feedburner.google.com/fb/a/mailverify?uri=helgeScherlundelearning
Enjoy what you've read, make sure you subscribe to my Email Updates

Monday, March 09, 2020

How the Mathematical Conundrum Called the ‘Knapsack Problem’ Is All Around Us | Science - Smithsonian

A litany of issues in business, finance, container ship loading and aircraft loading derive from this one simple dilemma, according to Elizabeth Landau, science writer and editor.

The "knapsack problem" is a widespread computing challenge—and no, it doesn't have to do just with literal backpacks.
Photo: golubovy / iStock

Imagine you’re a thief robbing a museum exhibit of tantalizing jewelry, geodes and rare gems. You're new at this, so you only brought a single backpack. Your goal should be to get away with the most valuable objects without overloading your bag until it breaks or becomes too heavy to carry. How do you choose among the objects to maximize your loot? You could list all the artifacts and their weights to work out the answer by hand. But the more objects there are, the more taxing this calculation becomes for a person—or a computer.

This fictional dilemma, the “knapsack problem,” belongs to a class of mathematical problems famous for pushing the limits of computing. And the knapsack problem is more than a thought experiment. “A lot of problems we face in life, be it business, finance, including logistics, container ship loading, aircraft loading — these are all knapsack problems,” says Carsten Murawski, professor at the University of Melbourne in Australia. “From a practical perspective, the knapsack problem is ubiquitous in everyday life.”
 
Researchers once took advantage of the problem’s complexity to create computer security systems, but these can now be cracked since the problem has been so well studied. Today, as technology capable of shattering the locks on our digital communications loom on the horizon, the knapsack problem may inspire new ways to prepare for that revolution...

“The problem the theoreticians started to look at was how efficiently a particular task can be carried out on a computer,” writes Keith Delvin in the book The Millennium Problems. For example: Given a list of 1 million museum artifacts with their weights and monetary values, and a backpack limited to 25 pounds, a computer would have to run through every possible combination to generate the single one with the most lucrative haul. Given an indefinite amount of time, a computer could use brute force to optimize large cases like this, but not on timescales that would be practical...

For those of us who are not computer scientists and face these kinds of problems in real life, how good are we? Murawski’s group finds preliminary results that when you give humans knapsack-like problems, we also struggle mightily. In small experiments in which participants were asked to fill a backpack on a computer screen with items carrying stated values and weights, people tended to have a harder time optimizing the backpack’s contents as the number of item options increased—the same problem computers have. The researchers say this finding may be related to “choice overload”: the way we freeze up when given too many choices, even in simple situations like buying jam at a grocery store. 
Read more...  

Recommended Reading

The Millennium Problems:
The Seven Greatest Unsolved Mathematical Puzzles Of Our Time

Source: Smithsonian