1
$\begingroup$

If you already have an approximation algorithm in hand, it's usually easier to prove that it is an α-approximation algorithm by merely analyzing the algorithm, than designing an approximation algorithm to achieve a α-approximation. That being said, what procedure or intuition should I have in mind to design a α-approximation algorithm?

$\endgroup$
4
  • $\begingroup$ It's often the case that it is difficult to come up with an answer to any problem, but once you see the solution it's so much clearer :-) So I don't know if this is anything special to do with approximation algorithms. I think you just need a good knowledge of the techniques, and experience as to what tends to work with various kinds of problems. You need to practice, there's no substitute for experience. $\endgroup$
    – Juho
    Nov 22 '17 at 21:39
  • 1
    $\begingroup$ This is a rather broad question. There's no automatic way of coming up with approximation algorithms. Creativity is required. Indeed, it is often challenging to design good approximation algorithms, and there are conferences devoted to the topic. $\endgroup$ Nov 22 '17 at 22:31
  • $\begingroup$ I think I've phrased my question a little vaguely. My question was more like what kind of intuition helps one to achieve a certain ratio of approximation. $\endgroup$
    – Ted
    Nov 22 '17 at 22:39
  • 1
    $\begingroup$ I’m voting to close this question as too broad, though I also think it’s primarily opinion based. This isn’t a question that has an answer, because different problems have wildly different algorithms. This is something best learned through a course or prolonged readings, not a three paragraph sketch on this site. There’s the beginning of a second question here, about carefully analyzing known algorithms vs. designing new algorithms to obtain a certain factor of approximation, but that’s not what the OP is asking about. $\endgroup$ Nov 23 '17 at 7:16

Browse other questions tagged or ask your own question.