English subtitles

← 17-01 Polynomial Time Approximation Scheme

Get Embed Code
1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. For some problems, there's no constant factor approximation algorithm unless P=NP
  2. or there are constant factor approximation algorithms
  3. but we know certain limits for how good that constant factor can get.
  4. There are other problems that allow for what is called a Polynomial-Time Approximation Scheme
  5. and the idea behind the polynomial-time approximation scheme is basically
  6. that if you put in more running time in to your algorithm,
  7. and that algorithm is called a polynomial-time approximation scheme,
  8. then you will get a better solution or a better guarantee for your solution,
  9. and depending on how good you want that guarantee to be,
  10. then again certain implications for the running time you have to put in.
  11. So, for an almost perfect solution,
  12. you will likely have to put in time that is pretty close to exponential time or even exponential time
  13. and for a solution that is--well, maybe only within a rather course bound of an optimal solution,
  14. you will need less time.
  15. Now, the NP complete problems that we have encountered so far
  16. obviously fall either into the category of having a constant factor approximation algorithm
  17. or admitting no such algorithm
  18. and that is why I'm going to introduce a new NP complete problem to you now called knapsack.
  19. A knapsack is a very simple to describe.
  20. Knapsack gives you as input a set of objects such as these here
  21. and each object has a size and a value and those are both integer number,
  22. so you have an integer size and an integer value and we're soon going to do an example for this,
  23. and then, additionally, you have given a container and that container has a limited capacity,
  24. and that capacity again is an integer,
  25. and the question you're trying to answer with knapsack is actually very simple,
  26. you're trying to ask the question,
  27. "What is the maximum value that I can put into this bag here while observing the limited capacity?"
  28. So the total sum of the size of the objects that I select to be in the knapsack,
  29. so say I select this object to be in the knapsack and this one here
  30. but I don't want this one here,
  31. then that means that the total size of these two objects cannot exceed the capacity of the container
  32. and among all other possibilities of putting objects
  33. into the container without exceeding maximum capacity,
  34. this gives me the best possible value,
  35. and of course, here for the values, we again do the sum to calculate the total value.
  36. Knapsack is known to be NP complete
  37. and now let's do a little example for this problem just to familiarize yourself with this
  38. and I'm going to give you a number of objects here, and of course,
  39. each of these objects has a size and a value.
  40. Now, my question to you is if I give you a container and that container has size 10,
  41. which objects out of these seven here should you put in to the container
  42. to maximize the value without exceeding the size here.
  43. Please check all the items that you should put in to the container to maximize the value.