I'm new here, so I apologize if this is not the appropriate place to ask this question.

I just started a graduate level course on approximate algorithms, and I am falling behind fast. The class is very theoretical and we are asked to prove approximation problems. We've covered traveling salesman problems, greedy algorithms, set cover, knapsack and makespan in the course of a couple weeks.

I understand the general sense of what the algorithms do, but I need help on intuition of what to do in proofs when trying to solve n-approximation problems.

What readings, topics, or skills will help my ability to solve approximation problems? After I see the solution, it makes sense, but I don't know how one would even start to think of that solution in the first place.

Thank you for any help you can offer.

  • 2
    $\begingroup$ Your course should provide numerous people you can ask for advice: the lecturer, tutors, TAs, your fellow students and so on. All of those people know what's actually in your course; we do not. $\endgroup$ – David Richerby Sep 23 '15 at 19:23
  • 4
    $\begingroup$ I'm voting to close this question as off-topic because it depends on circumstances we don't know, such as the content of the course and the learning resources available. Adding that information to the question would make it too specific to the asker's situation so not of use to anyone else. $\endgroup$ – David Richerby Sep 23 '15 at 19:24
  • $\begingroup$ Okay, thank you. I thought this was a more general question asking how to get better at solving approximation algorithms, perhaps I don't have enough knowledge about the material in order to frame a better question. @DavidRicherby $\endgroup$ – mtorres Sep 23 '15 at 20:08