knapsack problem

8 results back to index

Algorithms Unlocked by Thomas H. Cormen

bioinformatics, Donald Knuth, knapsack problem, NP-complete, optical character recognition, P = NP, Silicon Valley, sorting algorithm, traveling salesman

This optimization problem has obvious applications, such as deciding which items to take backpacking or what loot a burglar should choose to pilfer. The partition problem is really just a special case of the knapsack problem, in which the value of each item equals its weight and both W and V equal half the total weight. If we could solve the knapsack problem in polynomial time, then we could solve the partition problem in polynomial time. Therefore, the knapsack problem is at least as hard as the partition problem, and we don’t even need to go through the full reduction process to show that the knapsack problem is NP-complete. General strategies As you have probably realized by now, there is no one-size-fits-all way to reduce one problem to another in order to prove NP-hardness.

…

The hamiltonian-cycle problem is more restricted because each edge has only one of two “values”: present or absent. Look for special cases Several NP-complete problems are just special cases of other NPcomplete problems, much as the partition problem is a special case of Chapter 10: Hard? Problems 207 the knapsack problem. If you know that problem X is NP-complete and that it’s a special case of problem Y, then problem Y must be NPcomplete as well. That is because, as we saw for the knapsack problem, a polynomial-time solution for problem Y would automatically give a polynomial-time solution for problem X. More intuitively, problem Y, being more general than problem X, is at least as hard. Select an appropriate problem to reduce from It’s often a good strategy to reduce from a problem in the same, or at least a related, domain as the problem you’re trying to prove NPcomplete.

…

It doesn’t matter which set we say that y t is in, so let’s say that it’s in S 0 . Now, we know that the integers in S 0 sum to y, which means that the integers in S 0 other than y t must sum to y .y t/, or t. Since y ´ C t cannot also be in S 0 , we know that all the other integers in S 0 came from R. Hence, there is a subset of R that sums to t. Knapsack In the knapsack problem, we are given a set of n items, each with a weight and a value, and we ask whether there exists a subset of items whose total weight is at most a given weight W and whose total value is at least a given value V . This problem is the decision version of an optimization problem where we want to load up a knapsack with the most valuable subset of items, subject to not exceeding a weight limit.

Applied Cryptography: Protocols, Algorithms, and Source Code in C by Bruce Schneier

active measures, cellular automata, Claude Shannon: information theory, complexity theory, dark matter, Donald Davies, Donald Knuth, dumpster diving, Dutch auction, end-to-end encryption, Exxon Valdez, fault tolerance, finite state, heat death of the universe, information security, invisible hand, John von Neumann, knapsack problem, MITM: man-in-the-middle, Multics, NP-complete, OSI model, P = NP, packet switching, quantum cryptography, RAND corporation, RFC: Request For Comment, seminal paper, software patent, telemarketer, traveling salesman, Turing machine, web of trust, Zimmermann PGP

This is much more difficult than a superincreasing knapsack where, if you add one more weight to the sequence, it simply takes another operation to find the solution. Figure 19.1 Encryption with knapsacks. The Merkle-Hellman algorithm is based on this property. The private key is a sequence of weights for a superincreasing knapsack problem. The public key is a sequence of weights for a normal knapsack problem with the same solution. Merkle and Hellman developed a technique for converting a superincreasing knapsack problem into a normal knapsack problem. They did this using modular arithmetic. Creating the Public Key from the Private Key Without going into the number theory, this is how the algorithm works: To get a normal knapsack sequence, take a superincreasing knapsack sequence, for example {2, 3, 6, 13, 27, 52}, and multiply all of the values by a number n, mod m.

…

In general, the time required to solve this problem seems to grow exponentially with the number of items in the pile. The idea behind the Merkle-Hellman knapsack algorithm is to encode a message as a solution to a series of knapsack problems. A block of plaintext equal in length to the number of items in the pile would select the items in the knapsack (plaintext bits corresponding to the b values), and the ciphertext would be the resulting sum. Figure 19.1 shows a plaintext encrypted with a sample knapsack problem. The trick is that there are actually two different knapsack problems, one solvable in linear time and the other believed not to be. The easy knapsack can be modified to create the hard knapsack.

…

The public key is the hard knapsack, which can easily be used to encrypt but cannot be used to decrypt messages. The private key is the easy knapsack, which gives an easy way to decrypt messages. People who don’t know the private key are forced to try to solve the hard knapsack problem. Superincreasing Knapsacks What is the easy knapsack problem? If the list of weights is a superincreasing sequence, then the resulting knapsack problem is easy to solve. A superincreasing sequence is a sequence in which every term is greater than the sum of all the previous terms. For example, {1, 3, 6, 13, 27, 52} is a superincreasing sequence, but {1, 3, 4, 9, 15, 25} is not.

Life's Edge: The Search for What It Means to Be Alive by Carl Zimmer

3D printing, Albert Einstein, biofilm, call centre, coronavirus, COVID-19, discovery of DNA, double helix, Fellow of the Royal Society, gravity well, knapsack problem, lockdown, Loma Prieta earthquake, Louis Pasteur, low earth orbit, Lyft, microbiome, Richard Feynman, Schrödinger's Cat, Search for Extraterrestrial Intelligence, Silicon Valley, stem cell, Stuart Kauffman, tech worker, uber lyft

Now you must find the combination of items with the greatest value that is under a certain weight. Many businesses face practical versions of the Knapsack Problem. Airline companies want to figure out how to pack their planes so they can deliver the most valuable cargo using the least amount of fuel. Financial firms look for the best way to spread their funds across investments with different potential returns. There’s no simple equation to solve the Knapsack Problem, though. Researchers have filled books with strategies to get us close to the best solution. Slime molds may not be able to write books, but they can solve the Knapsack Problem. Audrey Dussutour, a scientist at Paul Sabatier University in Toulouse, France, and her colleagues brought their skill to light by translating the problem into the terms that matter to slime molds: food.

…

The slime molds built what looked remarkably like the American interstate highway system. They have mimicked Tokyo subways and Canada’s transportation network. It’s unsettling to mathematicians that slime molds can solve this kind of problem in a few days. It’s kept them busy for centuries. Another puzzle that has kept generations of mathematicians busy is known as the Knapsack Problem. Imagine you’re preparing for a hike, and you have to decide what to put in your knapsack. You can choose from a lot of different items that are more or less useful for the trip. But you also have to keep in mind the weight of your items, since you can’t pack an infinite number of them. You might tuck a deck of cards in your backpack so that you’d be able to pass the time on rainy mornings in the mountains playing poker.

…

See also genes and genetics Herzog, Carl, 90–92, 97, 99–101 hexuronic acid, 175 hibernation, 93–101 Hitler, Adolph, 177 HMS Beagle, 157 HMS Challenger, 152–54, 163–66 HMS Cyclops, 156, 160 HMS Lightning, 162 HMS Rattlesnake, 154–56, 156–57 Hoffman, Friedrich, 129 homeostasis, 93–101, 109, 124 hominins, 40–41 Hooker, Joseph, 217–18 hormones, 31, 58–60 Horowitz, Norman, 253, 254 hot springs, 216–17, 235, 236–38, 243 Hubbs, Carl, 213–14 Hubbs, Laura, 213–14 Hungary, 174, 176 Huxley, Thomas, 154–56, 157–58, 160–67, 219 hybrids, 213–14 hydrocarbons, 221, 236 hydrochloric acid, 73, 149 hydrogen sulfide, 216 Indian Institute of Technology Guwahati, 87 influenza, 206 information flows, 289–90 intelligence, 81–82, 88–89 International Committee on Taxonomy of Viruses, 210 International Space Station (ISS), 9–10, 242, 261 in vitro fertilization, 31–32 irritability, 139–43, 144–45, 158, 173 Jakosky, Bruce, 277–78 Jet Propulsion Laboratory (JPL), 250–55, 259, 260, 262 John of Naples, 21–22 Johnson Space Center, 255 Joseph II, Holy Roman Emperor, 143 Journal of the American Medical Association, 53 Joyce, Gerald, 199, 209 Jupiter, 260 Kasianowicz, John, 230 Kaufmann, Stuart, 283, 284–85, 286, 291 kelp, 5–6 kidneys, 52–53, 60, 70, 74 Knapsack Problem, 85–86 Koch, Christof, 33–34 Kolbe, Hermann, 150 Kompanichenko, Vladimir, 236 Lamarckian evolution, 270 Lavoisier, Antoine, 149 Lederberg, Joshua, 25, 34, 251, 254 Leduc, Stéphan, 265 Lee, Patrick, 27 legal standards of life and death, 25, 53–55, 55–62 “Legal Start of Life, The” (Washington Post), 25 Lenski, Richard, 115–16 Leonardo da Vinci, 280–81 Lewis, C.

The Logician and the Engineer: How George Boole and Claude Shannon Created the Information Age by Paul J. Nahin

air gap, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Any sufficiently advanced technology is indistinguishable from magic, Charles Babbage, Claude Shannon: information theory, Computing Machinery and Intelligence, conceptual framework, Edward Thorp, Fellow of the Royal Society, finite state, four colour theorem, Georg Cantor, Grace Hopper, Isaac Newton, John von Neumann, knapsack problem, New Journalism, Pierre-Simon Laplace, reversible computing, Richard Feynman, Schrödinger's Cat, Steve Jobs, Steve Wozniak, thinkpad, Thomas Bayes, Turing machine, Turing test, V2 rocket

Such massive parallelism is the fundamental origin of the quantum computer’s phenomenal speed. A class of famous, easy-to-understand problems (quite different from the factoring and search problems) that could also benefit from the massive parallelism of a quantum computer are the so-called knapsack problems. They are old problems, dating back at least to 1897, but they have modern applications, including cryptography. One knapsack problem asks the following question: given a stretchable knapsack that can hold a maximum weight of W, and n objects of individual weights w1, W2,…, wn, is there a subset of these objects that can be put into the knapsack that just achieves the knapsack’s weight capacity?

…

See also error detection Hartley, Ralph Hermite, Charles Hermitian matrix Hilbert, David Hopper, Grace Huxley, Thomas identity matrix infinity: countable; uncountable invertor gate, quantum. See also NOT “Investigation of the Laws of Thought, An” (Boole) irreversible: computation; logic gate J-K flip-flop Jobs, Steve Karnaugh, Maurice; map of Kelland, Philip Kelly, Jr., John Kelvin, Lord. See Thomson, William Kirchhoff, Gustav; circuit laws of knapsack problems Landauer, Rolf Laplace, Pierre-Simon latch Leibniz, Gottfried Levor, Norma logical operations: and; exclusive-or; inclusive-or; NOT. See also switch logic gates: irreversible; reversible. See also gates, logic “Logic of Chance” (Venn) machine (asynchronous); synchronous) majority logic map method.

Algorithms to Live By: The Computer Science of Human Decisions by Brian Christian, Tom Griffiths

4chan, Ada Lovelace, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, algorithmic bias, algorithmic trading, anthropic principle, asset allocation, autonomous vehicles, Bayesian statistics, behavioural economics, Berlin Wall, Big Tech, Bill Duvall, bitcoin, Boeing 747, Charles Babbage, cognitive load, Community Supported Agriculture, complexity theory, constrained optimization, cosmological principle, cryptocurrency, Danny Hillis, data science, David Heinemeier Hansson, David Sedaris, delayed gratification, dematerialisation, diversification, Donald Knuth, Donald Shoup, double helix, Dutch auction, Elon Musk, exponential backoff, fault tolerance, Fellow of the Royal Society, Firefox, first-price auction, Flash crash, Frederick Winslow Taylor, fulfillment center, Garrett Hardin, Geoffrey Hinton, George Akerlof, global supply chain, Google Chrome, heat death of the universe, Henri Poincaré, information retrieval, Internet Archive, Jeff Bezos, Johannes Kepler, John Nash: game theory, John von Neumann, Kickstarter, knapsack problem, Lao Tzu, Leonard Kleinrock, level 1 cache, linear programming, martingale, multi-armed bandit, Nash equilibrium, natural language processing, NP-complete, P = NP, packet switching, Pierre-Simon Laplace, power law, prediction markets, race to the bottom, RAND corporation, RFC: Request For Comment, Robert X Cringely, Sam Altman, scientific management, sealed-bid auction, second-price auction, self-driving car, Silicon Valley, Skype, sorting algorithm, spectrum auction, Stanford marshmallow experiment, Steve Jobs, stochastic process, Thomas Bayes, Thomas Malthus, Tragedy of the Commons, traveling salesman, Turing machine, urban planning, Vickrey auction, Vilfredo Pareto, Walter Mischel, Y Combinator, zero-sum game

The third, Lagrangian Relaxation, turns impossibilities into mere penalties, teaching the art of bending the rules (or breaking them and accepting the consequences). A rock band deciding which songs to cram into a limited set, for instance, is up against what computer scientists call the “knapsack problem”—a puzzle that asks one to decide which of a set of items of different bulk and importance to pack into a confined volume. In its strict formulation the knapsack problem is famously intractable, but that needn’t discourage our relaxed rock stars. As demonstrated in several celebrated examples, sometimes it’s better to simply play a bit past the city curfew and incur the related fines than to limit the show to the available slot.

…

“Well, 1|dj|∑ Cj is easy and that implies 1|pmtn, dj|∑ Cj is easy, so what do we know about 1|pmtn, rj, dj|∑ Cj?” “Nothing” [Lawler et al., “A Gift for Alexander!”; see also Lawler, “Old Stories”].) the problem becomes intractable: In fact, it’s equivalent to the “knapsack problem,” computer science’s most famously intractable problem about how to fill space. The connection between this scheduling problem and the knapsack problem appears in Lawler, Scheduling a Single Machine to Minimize the Number of Late Jobs. a certain time to start some of your tasks: What we are calling “start times” are referred to in the literature (we think somewhat ambiguously) as “release times.”

…

.; networking; websites fast connections geography of infrastructure of protocols and security and interrupt coalescing interruptions intractable problems defined equilibrium and relaxation and scheduling and Introduction to Relaxation Methods, An (Shaw) intuitive hunches investment strategies invitations involuntary selflessness Jacobson, Van Jain, Kamal James, William Jarvis, Richard Jaws (film) Jay, Francine Jeffreys, Harold Jet Propulsion Laboratory (JPL) jitter Jobs, Steve job search Johnson, Selmer Jones, William Joy of Less, The (Jay) judgment “just play the game” approach just society Kaelbling, Leslie Kahn, Robert “Bob” Kant, Immanuel Karels, Michael Karp, Richard Kaushik, Avinash Kayal, Neeraj Keats, John Keeping Found Things Found (Jones) Kenney, Richard Kepler, Johannes Kerr, Clark Keynes, John Maynard al-Khwārizmī King County Library System (KCLS) king of the hill Kipling, Rudyard Kirkpatrick, Scott Kleinrock, Leonard Kline, Charley knapsack problem Knuth, Donald Koomen, Pete Ladder tournaments Lagrange, Joseph-Louis Lagrangian Relaxation Lai, Tze Leung lancet liver fluke Lange, Rebecca language Lao Tzu Laplace, Pierre-Simon Laplace’s Law Lasso latency lateness, minimizing maximum laundry law enforcement Lawler, Eugene “Gene” “Lawn Tennis Tournaments” (Dodgson) Law of Gross Tonnage Lawrence, Peter A.

Crypto: How the Code Rebels Beat the Government Saving Privacy in the Digital Age by Steven Levy

Albert Einstein, Bletchley Park, Claude Shannon: information theory, cognitive dissonance, Compatible Time-Sharing System, computer age, disinformation, Donald Knuth, Eratosthenes, Extropian, Fairchild Semiconductor, information security, invention of the telegraph, Jim Simons, John Gilmore, John Markoff, John Perry Barlow, Kevin Kelly, knapsack problem, Marc Andreessen, Mitch Kapor, MITM: man-in-the-middle, Mondo 2000, Network effects, new economy, NP-complete, quantum cryptography, Ronald Reagan, Saturday Night Live, Silicon Valley, Simon Singh, Stephen Hawking, Steven Levy, Watson beat the top human players on Jeopardy!, web of trust, Whole Earth Catalog, zero-sum game, Zimmermann PGP, éminence grise

Since Merkle wanted these knapsacks to act as trapdoor one-way functions—something that would be easy for the right person to solve but nearly impossible for everyone else to crack—he needed to figure out a way to tame this difficult problem for the proper keyholder. He did this by first using a much easier variation of the knapsack problem called a superincreasing knapsack. In these problems, the list of weights is ordered in such a way that discovering the solution is a breeze. Merkle then figured out a way to transform that easy process to the far knottier problem that comes with figuring out the solution to a normal knapsack, where the weights aren’t so helpfully arranged.

…

“I’ve discreetly shown it to a few people here, and after listening to the resulting silence, I’ve concluded that the solution, if it exists, is at least not embarrassingly simple.” To be sporting about it, he made the task immeasurably easier, asking potential crackers to solve the problem with the difficulty of the knapsack problem set at a level so low that Merkle knew that there was at least a remote chance that someone might collect the reward. After that, he figured, he could raise the stakes and offer a higher bounty if someone cracked the real thing. “The point was that no one gave a damn about this stuff,” he says.

Competing on Analytics: The New Science of Winning by Thomas H. Davenport, Jeanne G. Harris

always be closing, Apollo 13, big data - Walmart - Pop Tarts, business intelligence, business logic, business process, call centre, commoditize, data acquisition, digital map, en.wikipedia.org, fulfillment center, global supply chain, Great Leap Forward, high net worth, if you build it, they will come, intangible asset, inventory management, iterative process, Jeff Bezos, job satisfaction, knapsack problem, late fees, linear programming, Moneyball by Michael Lewis explains big data, Netflix Prize, new economy, performance metric, personalized medicine, quantitative hedge fund, quantitative trading / quantitative finance, recommendation engine, RFID, search inside the book, shareholder value, six sigma, statistical model, supply-chain management, text mining, The future is already here, the long tail, the scientific method, traveling salesman, yield management

Its supply chain analysts try to optimize order quantities to satisfy constraints and minimize holding, shipping, and stock-out costs. In order to optimize its consumer goods supply chain, for example, it used an “integral min-cost flow problem with side constraints”; to round off fractional shipments, it used a “multiple knapsack problem using the greedy algorithm.” Logistics Management Sometimes a service company uses analytics with such skill and execution that entire lines of business can be created. United Parcel Service (UPS) took this route in 1986, when it formed UPS Logistics, a wholly owned subsidiary of UPS Supply Chain Solutions.

Secrets and Lies: Digital Security in a Networked World by Bruce Schneier

Ayatollah Khomeini, barriers to entry, Bletchley Park, business process, butterfly effect, cashless society, Columbine, defense in depth, double entry bookkeeping, drop ship, fault tolerance, game design, IFF: identification friend or foe, information security, John Gilmore, John von Neumann, knapsack problem, macro virus, Mary Meeker, MITM: man-in-the-middle, moral panic, Morris worm, Multics, multilevel marketing, mutually assured destruction, PalmPilot, pez dispenser, pirate software, profit motive, Richard Feynman, risk tolerance, Russell Brand, Silicon Valley, Simon Singh, slashdot, statistical model, Steve Ballmer, Steven Levy, systems thinking, the payments system, Timothy McVeigh, Y2K, Yogi Berra

This is the kind of math that can be used to create public-key cryptography; it involves modular arithmetic, exponentiation, and large prime numbers thousands of bits long, but you can elide the details. Today, there are a good half-dozen algorithms, with names like RSA, ElGamal, and elliptic curves. (Algorithms based on something called the knapsack problem were another early contender, but over the course of about 20 years they were broken every which way.) The mathematicals are different for each algorithm, but conceptually they are all the same. Instead of a single key that Alice and Bob share, there are two keys: one for encryption and the other for decryption.

Accelerando by Stross, Charles

book value, business cycle, call centre, carbon-based life, cellular automata, cognitive dissonance, commoditize, Conway's Game of Life, dark matter, disinformation, dumpster diving, Extropian, financial engineering, finite state, flag carrier, Flynn Effect, Future Shock, glass ceiling, gravity well, John von Neumann, junk bonds, Kickstarter, knapsack problem, Kuiper Belt, machine translation, Magellanic Cloud, mandelbrot fractal, market bubble, means of production, military-industrial complex, MITM: man-in-the-middle, Neal Stephenson, orbital mechanics / astrodynamics, packet switching, performance metric, phenotype, planetary scale, Pluto: dwarf planet, quantum entanglement, reversible computing, Richard Stallman, satellite internet, SETI@home, Silicon Valley, Singularitarianism, Skinner box, slashdot, South China Sea, stem cell, technological singularity, telepresence, The Chicago School, theory of mind, Turing complete, Turing machine, Turing test, upwardly mobile, Vernor Vinge, Von Neumann architecture, warehouse robotics, web of trust, Y2K, zero-sum game

By the time they finish, he's aching, and she shows him how to use the bidet. Everything is crystal clear, and her touch is electrifying. While she showers, he sits on the toilet seat lid and rants about Turing-completeness as an attribute of company law, about cellular automata and the blind knapsack problem, about his work on solving the Communist Central Planning problem using a network of interlocking unmanned companies. About the impending market adjustment in integrity, the sinister resurrection of the recording music industry, and the still-pressing need to dismantle Mars. When she steps out of the shower, he tells her that he loves her.