English 字幕

← 14-31 What To Do In Practice Solution



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

  1. And the answer here is that I would recommend that Alice run both algorithms
  2. because both algorithms, if you look at them, are very simple so they can be implemented
  3. to run very fast even if the input graph is very large.
  4. So if she can first, for example, run the take 2 algorithm and then she already has a solution
  5. for which she has a guaranteed, so running the take 2 algorithm will defer some information
  6. about an optimum solution and that is the optimum solution cannot be smaller than some quantity x.
  7. And if she then runs the greedy algorithm, she can just see if the greedy algorithm
  8. gives her a solution that is better than the take 2 algorithm.
  9. In this case, she should take the greedy solution or if it produces adverse solution,
  10. so if by some accident she's running it on a graph that has the same properties than the one that
  11. we just constructed to trick the algorithm, then she can take the solution,
  12. and in this way, she gets the best of both algorithms.
  13. She gets the good performance or the generally good performance of this algorithm,
  14. but she ensures that she is within certain guarantees.
  15. The important thing here to keep in mind is just because an approximation algorithm
  16. sounds like it make sens or sounds like it is a good idea, doesn't really mean that it is a good idea.
  17. It could be a good idea, but unless you analyze the algorithms
  18. and try to prove that properties--you'll never know.