The tag is currently much more popular than the tag , although both concern approximation algorithms. Should we get rid of the second?

  • $\begingroup$ Hmm, well what even are approximation algorithms? I have encountered different answers to the following statements: 1. An approximation algorithm gives a solution with a formal guarantee of the quality 2. An approximation algorithm always solves a combinatorial problem 3. An approximation algorithm always solves an objective and well-defined optimisation problem... I think some of those answers are wrong, but they are nevertheless used by experts in certain CS fields. I'm not sure what I should conclude here, other that classifying these questions may be difficult. $\endgroup$ – Discrete lizard Nov 22 '20 at 15:01
  • $\begingroup$ (of course, here I haven't even touched on the difference between an approximation algorithm and an algorithm that returns an "approximation" or "approximate solution".) $\endgroup$ – Discrete lizard Nov 22 '20 at 15:02
  • $\begingroup$ An approximation algorithm solves a combinatorial optimization problem with a worst-case guarantee on the approximation ratio. $\endgroup$ – Yuval Filmus Nov 22 '20 at 15:05

You must log in to answer this question.

Browse other questions tagged .